原题链接
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> #include <cmath> #include <queue> #define MOD 998244353 #define maxn 50005 #define INF 1e18 using namespace std; typedef long long ll; int vis[1000005]; int main(){ // freopen("in.txt", "r", stdin); int n; while(scanf("%d", &n) == 1){ int a; memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++){ scanf("%d", &a); vis[a] = 1; } int maxs = 1; for(int i = 2; i <= 1000000; i++){ int cnt = 0; for(int j = i; j <= 1000000; j += i){ if(vis[j]) cnt++; if(cnt == 2) break; } if(cnt == 2) maxs = i; } printf("%d\n", maxs); } return 0; }