题意：给你两个等长的数列，让你在两个数列中各选择一个数字，使得这两个数的gcd是这n * n种组合中最大的。

思路：如果上来就考虑分解因式什么的，就想偏了，假设数列1的最大数为max1，数列2的最大数为max2，我们知道，这个max_gcd一定是在

1~max(max1,max2)中间的。我们一 一 枚举（从大到小）来验证。

我们在验证 i 的时候，是否要用数列中的每一个数来 % 一下 i ，看看是否能整除呢？

答案是不用的，我们可以仅仅验证 i 的倍数的数字在这个数列中是否存在。这样扫一遍的复杂度为 n / i 。

验证时总的复杂度为nlogn。

详见代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
const int maxn2 = 500005;

bool mark1[maxn],mark2[maxn];
int store1[maxn2],store2[maxn2];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;++i){
        scanf("%d",&store1[i]);
        mark1[store1[i]] = true;
    }
    for(int i = 0;i < n;++i){
        scanf("%d",&store2[i]);
        mark2[store2[i]] = true;
    }
    sort(store1,store1 + n);
    sort(store2,store2 + n);
    int maxx = max(store1[n - 1],store2[n - 1]);
    int ans = 0;
    for(int i = maxx;i >= 1;+--i){
        int a = 0,b = 0;
        int temp = i;
        while(temp <= maxx){
            if(mark1[temp]) ++a;
            if(mark2[temp]) ++b;
            if(a > 0 && b > 0){
                ans = i;
                break;
            }
            temp += i;
        }
        if(a > 0 && b > 0) break;
    }
    int out = 0;
    for(int i = n - 1;i >= 0;--i){
        if(store1[i] % ans == 0){
            out += store1[i];
            break;
        }
    }
    for(int i = n - 1;i >= 0;--i){
        if(store2[i] % ans == 0){
            out += store2[i];
            break;
        }
    }
    printf("%d\n",out);
    return 0;
}

 

版权声明：本文为tiberius原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/tiberius/p/9310993.html