题目来源： 

基准时间限制：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示例

49152516

Output示例

5

从数组中最大的数开始试验，看其倍数 是否满足出现了两次的要求，出现了两次，还是从最大的数开始递减的话，说明这个数一定是这些数中的最大的最大公约数。

代码：

#include 
    
       #include 
     
        #include 
      
         #include 
       
          #include 
        
           #include 
         
           #pragma warning(disable:4996) using namespace std;int n;int val[50005];int cnt[1000005];int main(){ //freopen("i.txt", "r", stdin); //freopen("o.txt", "w", stdout); int i, j, maxn, sum; scanf("%d", &n); maxn = 0; for (i = 0; i < n; i++) { scanf("%d", val + i); cnt[val[i]]++; maxn = max(maxn, val[i]); } for (j = maxn; j >= 1; j--) { sum = 0; for (i = j; i <= maxn; i = i + j) { sum += cnt[i]; if (sum >= 2) { break; } } if (sum >= 2) { cout << j << endl; break; } } //system("pause"); return 0;}
         
        
       
      
     
    

版权声明：本文为博主原创文章，未经博主允许不得转载。