2020牛客暑期多校训练营（第四场）Harder Gcd Problem

2020牛客暑期多校训练营（第四场）Harder Gcd Problem

题目大意：

给你n个数，从1到n，让你从这些数中选出两个集合，要求两个集合的大小相等，并且没有一个数既属于第一个集合A又属于第二个集合B，求最大的集合大小使得这个集合有一个排列 (gcd(a_{pi},b_{qi})>1)

题解：

这个题目求每一个数的最小质因子，然后分类。

分完之后存下来，然后先内部进行消化，也就是内部两两之间进行组合，然后如果还剩下一个，那么就和最小的质因子也就是2进行判断，是否存在 (2*x<=n) 存在即两两进行组合。

#include <bits/stdc++.h>
#define debug(x) printf("debug:%s=%lld
",#x,x);
//#define debug(x) cout << #x << ": " << x << endl
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
const int mod = 1e9+7;
int isp[maxn],cnt,v[maxn];
void init() {
    cnt = 0;
    memset(v, 0, sizeof(v));
    for (int i = 2; i < maxn; ++i) {
        if (!v[i]) {
            v[i] = i;
            isp[cnt++] = i;
        }
        for (int j = 0; j < cnt; ++j) {
            if (1ll * i * isp[j] >= maxn) break;
            v[i * isp[j]] = isp[j];
        }
    }
}
vector<int>num[maxn];
bool vis[maxn];
int ans1[maxn],ans2[maxn];
int main() {
    int t;
    init();
    scanf("%d", &t);
    while (t--) {
        int n, now = 0;
        scanf("%d", &n);
        for (int i = 0; i <= n; i++) num[i].clear(), vis[i] = false;
        for (int i = 2; i <= n; i++) num[v[i]].push_back(i);
        for (int i = n; i >= 1; i--) {
            int x = isp[i];
            int len = num[x].size(), from = 0;
            if (!len) continue;
            if (len & 1) {
                if (x * 2 <= n) {
                    from = 1, ++now;
                    ans1[now] = x, ans2[now] = 2*x;
                    vis[2*x]=true;
                }
            }
            for (int j = from; j < len; j+=2) {
                if (j + 1 >= len) break;
                ++now;
                ans1[now] = num[x][j];
                ans2[now] = num[x][j + 1];
            }
        }
        for(int i=0;i<num[2].size();i++){
            int x = num[2][i];
            if(vis[x]) continue;
            num[0].push_back(x);
        }
        for(int i=0;i<num[0].size();i+=2){
            if(i+1>=num[0].size()) break;
            ++now;
            ans1[now]=num[0][i];
            ans2[now]=num[0][i+1];
        }
        printf("%d
",now);
        for(int i=1;i<=now;i++) printf("%d %d
",ans1[i],ans2[i]);
    }
    return 0;
}