51nod-1179-最大的gcd(数学)

1179 最大的最大公约数

题目来源： SGU

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

关注

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

  注意到数据最大是100w，我们可以用tot[i]记录i出现的次数，然后枚举所有的可能答案i，统计i,i*2,i*3...i*k的总数s，如果s>=2表示i可以达到。这个过程类似于素数筛的，
所以复杂度是nlog(n);

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int s[];

 int tot[];

 int main()

 {

     int n,i,j,k;

     scanf("%d",&n);

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

       scanf("%d",s+i);

       tot[s[i]]++;

      }

     for(i=;i>=;--i){

                     int tmp=;

                     for(j=i;j<=;j+=i){

                             tmp+=tot[j];

                             if(tmp>=) break;

                         }

                         if(tmp>=){

                             cout<<i<<endl;

                             break;

                             }

                 }

     return ;

 }

巴特西

51nod-1179-最大的gcd(数学)

最新文章

热门文章