51nod:1179 最大的最大公约数

51nod:1179 最大的最大公约数

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#include#include#includeusing namespace std;#define maxn 1001000int 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。