51Nod - 1179

给出N个正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。

 

Input第1行：一个数N，表示输入正整数的数量。(2 <= N <= 50000) 
第2 - N + 1行：每行1个数，对应输入的正整数.(1 <= Sii <= 1000000)Output输出两两之间最大公约数的最大值。Sample Input

4

9

15

25

16

Sample Output

5

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <iomanip>

 #include <string>

 #include <sstream>

 #include <algorithm>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;

 const int MOD = 1e9 + ;

 #define MemI(x) memset(x, -1, sizeof(x))

 #define Mem0(x) memset(x, 0, sizeof(x))

 #define MemM(x) memset(x, 0x3f, sizeof(x));

 //这解法的时间复杂的不会算，因为最坏情况可能是要考虑各个数互质

 //先算出所有数中最大的数 mx ，然后枚举 mx 到 1 的所有数作为公约数

 int num[MAXN];

 int main()

 {

     Mem0(num);

     int n, t;

     cin >> n;

     int i, j, mx = ;

     for(i = ;i < n;++i)

     {

         cin >> t;

         num[t]++;

         mx = max(t, mx);

     }

     int flag = ;

     for(i = mx;i >  && flag < ;--i)

     {

         flag = ;

         // j 表示公约数的倍数

         for(j = i;j <= mx && flag < ;j += i)

             flag += num[j];

     }

     //这里注意上面循环跳出 flag 时，是进行过 --i 的

     cout << i + << endl;

     return ;

 }