2020牛客暑期多校第四场 H - Harder Gcd Problem（思维/构造）

传送门

---

大意：给出若干数，从中选出若干个不互质的整数对，问最多能选出多少对

比赛时尝试过筛最小质因子最大质因子或者先考虑只有一个质因子的数之类的瞎搞，没搞出来，实际上这题的关键一步还是比较难想到的

正解：首先不难知道$n/2$n/2以内的数才有效，因为两个不互质的数最小公因数是$2$2，那么我们考虑枚举$n/2$n/2之内的每一个质数$i$i，找出范围内其所有的倍数，不难发现实际上只需要对这些倍数配对即可，但是这些倍数的个数可能是奇数也可能是偶数，如果是奇数的话，留哪一个呢？因为最小的质数是$2$2，因此如果倍数集合的大小为奇数，每次留下$2$2的倍数那个数，那么最后所有集合剩下的$2$2倍数一定可以两两配对，最后再贪心配对即可

#include <bits/stdc++.h>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+100;

vector<pii> ans;
int prime[maxn],tot;
bool isprime[maxn],vis[maxn];

void euler(){
    memset(isprime,1,sizeof isprime);
    isprime[0]=isprime[1]=0;
    for(int i=2;i<maxn;i++){
        if(isprime[i]) prime[tot++]=i;
        for(int j=0;j<tot && i*prime[j]<maxn;j++){
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0) break;
        }
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    euler();
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        vector<int> res;
        ans.clear();
        memset(vis,0,sizeof vis);
        for(int i=n/2;i>=2;i--) if(isprime[i]){
            vector<int> tmp;
            for(int j=i;j<=n;j+=i) if(!vis[j]){
                tmp.push_back(j);
                vis[j]=1;
            }
            int x=tmp.size();
            if(x&1){
                tmp.erase(find(tmp.begin(),tmp.end(),2*i));
                res.push_back(2*i);
            }
            for(int j=0;j+1<tmp.size();j+=2)
                ans.push_back(mkp(tmp[j],tmp[j+1]));
        }
        for(int i=0;i+1<res.size();i+=2)
            ans.push_back(mkp(res[i],res[i+1]));
        printf("%d\n",ans.size());
        for(auto i: ans){
            printf("%d %d\n",i.fi,i.se);
        }
    }
    return 0;
}