Harder Gcd Problem

题目链接：https://ac.nowcoder.com/acm/contest/5669/H
题目描述：
把1~N的数选尽量多的组，使得每组gcd大于1.
输出任意一种方案。
做法：
看到匹配gcd大于1的，我们很容易想到质数，质数和除其倍数的数的gcd都是等于1的。
考虑哪些数字是不可能在匹配里的。
首先1不可能在匹配里。
大于n/2的质数p，也是可以直接扔掉的。
接下来会发现其他的数都不太好扔了，它们都有可能与别的数匹配。
考虑怎么匹配。
<=n/2的p它们是怎么匹配的？现在考虑一个质因子p，会有2p，3p，4p...，kp现在还有一个问题就是这些数有可能被别的数匹配过了，我们的策略中需要考虑到这点。我们发现列举出来的这些数字它们两两都是gcd>1的，那么至少能取[k/2]组(如果它们之前都没有与别的数匹配)。
而我们发现如果我们倒序枚举，只需要考虑奇数的时候剩下哪个留给下面去配对就可以了。p的倍数数列中，2p很显眼，因为对于所有不同的质因子，它们的2p也是可以自由匹配的。
策略：
如果为奇数，则留下2p，其他随意匹配
如果为偶数，则两两随意匹配。
简单的证明这个策略是最优的：
之前已经把不能匹配的数去掉了，然后对于能匹配的数，我们都是尽量匹配，如果最后剩下了，那就是多余的了，即使剩下这1个数字也没有关系。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+7;
int prime[MAXN], cnt;
bool vis[MAXN];
int ans[MAXN];
void Prime()
{
    for(int i = 2; i <= MAXN; i++) {
        if(!vis[i]) {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt ; j++) {
            if(i * prime[j] > MAXN) break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;    //当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。 
        }
    }
}
bool v[MAXN];
int main()
{
    int t;
    scanf("%d",&t);
    Prime();
    while(t--)
    {
        int n, m = 0;
        memset(v, 0 , sizeof(v));
        scanf("%d",&n);
        int up = upper_bound(prime + 1, prime + cnt + 1, n / 2) - prime - 1;
        for(int i = up; i >= 1; i--) {
            for(int j = prime[i]; j <= n; j+=prime[i]) {
                if(v[j] == 1 || j == prime[i] << 1) {
                    continue;
                }
                ans[++m] = j;    //肯定是偶数个，完全不需要pair来记录 
                v[j] = 1;
            }
            if(m % 2 == 1) {    //2p加进来容易，扔出去难，我们可以先不加2p，有需要再加
                v[prime[i] << 1] = 1;
                ans[++m] = prime[i] << 1;
            } 
        }
        printf("%d\n",m/2);
        for(int i = 1; i <= m; i+=2) {
            printf("%d %d\n", ans[i], ans[i+1]);
        }
    }
}