水 hdu5208 2015-04-20 21:03 36人阅读 评论(0) 收藏

题意：  

选择数列中两个数，使得最大公约数最大

分析：

类似筛选法，因为数值不大，可以用b[i]计算i是多少个数的因子。最后取最大的i即可。

#include <bits/stdc++.h>
//#define OPEN_FILE
using namespace std;

const int MAXN = 100001;
int main()
{
#ifdef OPEN_FILE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // OPEN_FILE
    int T, cas, n, i, maxa, x, j, ans;
    int a[MAXN], b[MAXN];
    scanf("%d", &T);
    for(cas = 1; cas <= T; cas++){
        scanf("%d", &n);
        maxa = -1;
        memset(a, 0, sizeof(a));
        for(i = 1; i <= n; i++){
            scanf("%d", &x);
            a[x]++;
            maxa = max(maxa, x);
        }
        memset(b, 0, sizeof(b));
        for(i = 2; i <= maxa; i++){
            for(j = 1; j * i <= maxa; j++){
                if(a[i * j] == 0) continue;
                b[i] += a[i * j];
            }
            if(b[i] >= 2){
                ans = i;
            }
        }
        printf("Case #%d: %d
", cas, ans);
    }
}

版权声明：本文为博主原创文章，未经博主允许不得转载。