1179 最大的最大公约数

题目来源： SGU

基准时间限制：1 秒空间限制：131072 KB 分值: 40

给出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示例

Output示例

5
思路：枚举最大公约数，然后用类似筛法的方式判断当前的约数是否在原数组中存在两个或两个以上的数是他的倍数。复杂度n*log(n);

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<string.h>
 5 #include<queue>
 6 #include<math.h>
 7 #include<set>
 8 #include<vector>
 9 #include<string.h>
10 using namespace std;
11 typedef long long LL;
12 int ans[1000005];
13 int main(void)
14 {
15     int n,m;
16     scanf("%d",&n);
17     int i,j;
18     memset(ans,0,sizeof(ans));
19     int t;
20     int maxx = 0;
21     for(i = 0; i < n; i++)
22     {
23         scanf("%d",&t);
24         ans[t]++;
25         maxx = max(maxx,t);
26     }
27     LL c = 0;int v ;
28     for(i = maxx; i >= 1 ; i--)
29     {
30          v = 0;
31         for(j = 1; ((LL)i*(LL)j)<= maxx ; j++)
32         {
33             v+=ans[i*j];
34             if(v>=2)
35             {
36                 c = i;
37                 break;
38             }
39         }
40         if(c)
41             break;
42     }
43     printf("%d
",c);
44     return 0;
45 }

油！油！you@