第四场H-Harder Gcd Problem

题意：
给出1-n的数字，让选择m对数字，让gcd(a_i,b_i)>1，让m尽可能大，并且输出这m对对应的数字。

思路：
整体的思路就是筛法+贪心。
不过我代码写的比较复杂，比较low。。
首先就是筛法，把n个数的质因子种类数，和最小质因数维护出来。cnt[i]表示i的质因子有多少种，mi[i]表示i的最小质因数是多少
开一个vector 其中z[i]表示含有质因子i的数字的集合。
然后我们去进行两个数字的匹配，这里去贪心的选择。
首先我们应该倒序 即从z[n]到z[1]里面去选择。为什么？ 因为含有的质因子越大，可以匹配到的另一个的个数越少，所以优先倒序来。
对于具体到某个z[i] 这里还需要一次贪心，比如 z[2][0]=2,z[2][1]=6,z[2][2]=8,z[2][3]=10 对z[2]排序应该是这样的 2 8 10 6
对于一个数的质因子的种类越多，能匹配的个数也越多，所以对于具体的z[i] 应该先按照质因子种类数从小到大排序，对于质因子种类数相同的，最小质因数越大，我们就优先对他进行匹配。
总体复杂度O（T * nlogn）

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
#define int long long
bool vis[maxn];
vector<int> z[maxn],qq;
int cnt[maxn],mi[maxn];
bool cmp(int x,int y){
    if(cnt[x]==cnt[y]) return mi[x]>mi[y];
    return cnt[x]<cnt[y];
}
signed main()
{

    int t;cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        qq.clear();
        for(int i=1; i<=n; i++)
            vis[i]=0,z[i].clear(),cnt[i]=0,mi[i]=1e9;
        for(int i=2;i<=n;i++){
            if(!vis[i]){
                for(int j=i;j<=n;j+=i){
                    vis[j]=1;
                    mi[j]=min(mi[j],i);
                    cnt[j]++;
                    z[i].push_back(j);
                }
            }
        }
        for(int i=1;i<=n;i++) vis[i]=0;
        int ans=0;
        for(int i=n; i; i--)
        {
            sort(z[i].begin(),z[i].end(),cmp);
            int a=-1,b=-1;
            for(int j=0; j<z[i].size(); j++)
            {
                if(!vis[z[i][j]])
                {
                    if(a==-1)
                    {
                        a=z[i][j];
                    }
                    else if(b==-1)
                    {
                        b=z[i][j];
                    }
                }
                if(a!=-1 && b!=-1)
                {
                    qq.push_back(a);
                    qq.push_back(b);
                    ans++;
                    vis[a]=vis[b]=1;
                    a=b=-1;
                }
            }
        }
        cout<<ans<<endl;
        for(int i=0; i<ans; ++i)
            cout<<qq[2*i]<<" "<<qq[2*i+1]<<endl;

    }
    return 0;
}