51Nod_1179 最大的最大公约数

本文主要是介绍51Nod_1179 最大的最大公约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

4
9
15
25
16

Output示例

5

题解：求给出的数中两两之间最大公约数的最大值，如果暴力求出两两之间的最大公约数再进行比较一定会超时。逆向思考，假设我们已经找到问题的解了，只需去判断它是否是给出的数中的某几个数的最大公约数，我们从给出的数的最大值开始枚举，不断减一，直到至少有两个数是它的倍数，程序用a[i]记录给出的数中i出现的次数，

AC的C++程序：

#include<iostream>using namespace std;const int N=1000000;int a[N+1];int main()
{int n,x,end=1,ans=1;cin>>n;for(int i=1;i<=n;i++){cin>>x;a[x]++;end=max(end,x);}for(int j=end;j>=1;j--){//从给出的数中的最大值开始枚举，不断减一int cnt=0;for(int i=j;i<=N;i+=j){cnt+=a[i];if(cnt>=2)break;}if(cnt>=2){//如果有至少两个数是j的倍数，说明j就是所求的最大公约数ans=j;break;}}cout<<ans<<endl;return 0;
}

 

这篇关于51Nod_1179 最大的最大公约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---