Codeforces-B-Divisors of Two Integers(思维技巧)
Recently you have received two positive integer numbers xx and yy. You forgot them, but you remembered a shuffled list containing all divisors of xx (including 11 and xx) and all divisors of yy (including 11 and yy). If dd is a divisor of both numbers xx and yy at the same time, there are two occurrences of dd in the list.
For example, if x=4x=4 and y=6y=6 then the given list can be any permutation of the list [1,2,4,1,2,3,6][1,2,4,1,2,3,6]. Some of the possible lists are: [1,1,2,4,6,3,2][1,1,2,4,6,3,2], [4,6,1,1,2,3,2][4,6,1,1,2,3,2] or [1,6,3,2,4,1,2][1,6,3,2,4,1,2].
Your problem is to restore suitable positive integer numbers xx and yy that would yield the same list of divisors (possibly in different order).
It is guaranteed that the answer exists, i.e. the given list of divisors corresponds to some positive integers xx and yy.
Input
The first line contains one integer nn (2≤n≤1282≤n≤128) — the number of divisors of xx and yy.
The second line of the input contains nn integers d1,d2,…,dnd1,d2,…,dn (1≤di≤1041≤di≤104), where didi is either divisor of xx or divisor of yy. If a number is divisor of both numbers xx and yy then there are two copies of this number in the list.
Output
Print two positive integer numbers xx and yy — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.
Example
input
Copy
10
10 2 8 1 2 4 1 20 4 5
output
Copy
20 8
思路:先选出最大的,然后去遍历是他取模为0的并标记一下,其余的存在另一个数组里,在筛选出最大的
代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[150];
int b[150];
int vis[10005];
int main()
{
int n;
cin>>n;
for(int t=0;t<n;t++)
{
scanf("%d",&a[t]);
}
sort(a,a+n);
int l=a[n-1];
int s=0;
for(int t=0;t<n;t++)
{
if(l%a[t]==0&&vis[a[t]]==0)
{
vis[a[t]]=1;
continue;
}
else
{
b[s++]=a[t];
}
}
sort(b,b+s);
cout<<l<<" "<<b[s-1]<<endl;
return 0;
}
最新文章
- Building good docker images
- [Android Rro] SDK JAR
- 移动端页头推荐配置 出现找不到favicon.ico错误原因和解决方法
- flash builder的编译缓存
- 【转】CSS中怎么让DIV居中
- oracle11g导入dmp文件(根据用户)
- 学习strcat与strcpy
- LR(1)表驱动语法分析设计图表
- linux系统下解决getch()输入数值不回显示
- JavaScript Math 对象的常用方法
- 05-迪米特法则(LOD 又名: 最少知道原则)
- 出现System.web.mvc冲突的原因及解决方法CS0433
- iOS 6 & iOS 7 的适配笔记
- Flutter 控件之 AppBar 和 SliverAppBar
- HTML中button和input button的区别
- Thrift语法参考
- p4980 polya定理
- 容器,Docker, Kubernetes和Kyma,以及Kyma对SAP的意义
- 06-spring学习-自动装配
- JavaScript常用知识点整理——思维导图