51Nod－1179－最大的最大公约数

ACM模版

描述

题解

由于正整数的上限为1e6，不是太大，所以，可以开一个一百万的数组，用来存储正整数出现的次数，并且记录下最大的正整数MAXA，MAXA是可能的最大公约数的上限，然后从MAXA到1开始检索，当检索到cnt大于等于2时，说明这个数是最大公约数。

代码

#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int MAXN = 1e6 + 10; int S[MAXN]; int main() { int n; while (~scanf("%d", &n)) { memset(S, 0, sizeof(S)); int MAXA = 0, x; for (int i = 0; i < n; i++) { scanf("%d", &x); S[x]++; if (x > MAXA) { MAXA = x; } } int ans = 1; for (int j = MAXA; j >= 1; j--) { int cnt = 0; for (int i = j; i <= MAXA; i += j) { cnt += S[i]; if (cnt >= 2) { ans = j; goto out; } } } out: printf("%d\n", ans); } return 0; }