51-Nod 1179

传送门

求两两之间的最大公约数

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int maxn = 5e4 + 10;
const int maxm = 1e6 + 10;
int A[maxn];
int cnt[maxm];
int N;



int main() {
    memset(cnt, 0, sizeof(cnt));
    int ans = 0;
    int mx = 1;    

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        mx = max(mx, A[i]);
        cnt[A[i]]++;
    }
    sort(A, A + N);
    for (int i = N - 1; i ; i--) if (cnt[A[i]] >= 2) {
        ans = A[i];
        break;
    }
    bool flag = 0;
    for (int i = (mx + 1) / 2; i >= ans; i--) {
        int c = 0;
        for (int j = i; j <= mx && c < 2; j += i) {
            c += cnt[j];
        }
        if (c >= 2) {
            ans = i;
        }
    }
    printf("%d
", ans);
    return 0;
}