描述
给出 N 个正整数,找出 N 个数两两之间最大公约数的最大值。
例如:N = 4,4个数为:9 15 25 16,两两之间最大公约数的最大值是15同25的最大公约数5。
Input
第1行:一个数N,表示输入正整数的数量。(2 <= N <= 50000)
第2 – N + 1行:每行1个数,对应输入的正整数.(1 <= S[i] <= 1000000)
Output
输出两两之间最大公约数的最大值。
Input示例
4
9
15
25
16
Output示例
5
思路
找出两两之间的最大公因数的最大值,怎么说 50000×50000×gcd
也会超时的哦!
那么我们就采用类似于桶的结构,把每一个数先保存在桶中,然后从大到小查找,判断是否为某数的因子,找到之后跳出循环,输出。
AC 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1001000
int num[maxn];
int main()
{
int n,i,j,sum,t,mmax=0;
cin>>n;
for(i=1; i<=n; i++)
{
cin>>t;
num[t]++;
mmax=max(mmax,t);
}
for(i=mmax; i>=1; i--)
{
sum=0;
for(j=i; j<=mmax; j+=i)
{
sum+=num[j];
if(sum>=2)break;
}
if(sum>=2)break;
}
printf("%d\n",i);
return 0;
}