最大的最大公约数-数论

 

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

4

9

15

25

16

Output 示例

5

 

分析：

这道题目，如果暴力肯定超时。考虑到最大的公约数肯定<=1000000.所以可以从1000000开始一直枚举到1，对于每一个枚举的数，如果同时是至少两个数的约数，那么就输出即可。

如何确定这个数是否是一个数的约数，不能直接枚举50000个数，首先cnt【N个数】=1，然后对于一个数是否是两个数的约数可以直接累加这个数，然后sum+=cnt[累加值]。

比如示例，如果枚举到5了，那么sum+=cnt[5],sum+=cnt[10],sum+=cnt[15],sum+=cnt[20],sum+=cnt[25],此时发现sum=2了，那就5肯定同时是两个数的约数，又因为是从1000000到1枚举，所以找到的第一个一定是最大的最大公约数。

 

复杂的n*(sum(N/i)，i=[1-1000000]),这里想象sum(N/i)可能很大,但是实际很快，比如如果i=1，那么在计算cnt[]时，sum肯定很快就=2了，因为最大公约数是1，前两个数就满足了，如果i=2时，同样，前两个偶数就满足了。。。。复杂度接近O（nLogN）

代码：

 

#include <iostream>  
#include <cstdlib>  
#include <cstring>  
using namespace std;  
int cnt[1000001];  
int main()  
{  
    int N;  
    int MAX = 0;  
    int num;  
    while (cin >> N)  
    {  
        MAX = 0;  
        memset(cnt,0,sizeof(cnt));  
        for (int i = 0; i < N; ++ i)  
        {  
            cin >> num;  
            ++cnt[num];  
            if (num > MAX)  
            {  
                MAX = num;  
            }  
        }  
  
          
        for (int i = MAX; i >= 1; -- i)  
        {  
            int sum = 0;  
            for (int j = i; j <= MAX; j += i)  
            {  
                sum += cnt[j];  
                if (sum >= 2)  
                {  
                    break;  
                }  
            }  
            if (sum >= 2)  
            {  
                cout << i << endl;  
                return 0;  
            }  
        }  
    }  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,