H-Harder Gcd Problem

链接：https://ac.nowcoder.com/acm/contest/5669/H
来源：牛客网

题意：

给你一个1-n的数，让你将n个数分成两堆，且对应的两个数gcd不为1，也就是不互质

solution：

可以从最大的质数k开始往后构造，找出尽可能多的k的奇数倍，如果k的
奇数倍的个数为奇数，就跟2*k进行匹配。然后循环找出前一个最大的质数，最后将2的倍数进行匹配。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
int prime[1000005],not_prime[1000005],num=0;
int t,n,mark[2000005];
vector<P> e;
int main()
{
    not_prime[1]=1;
    for(int i=2;i<=200000;i++)
    {
        if(!not_prime[i])
        {
            prime[num++]=i;
            for(int j=2*i;j<=200000;j+=i)
                not_prime[j]=1;
        }
    }
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        int k;
        for(int i=0;;i++)
        {
            if(prime[i]<=n/2)k=i;
            else break;
        }
        for(int i=1;i<=n;i++)
            mark[i]=1;
        e.clear();
        //cout<<1;
        for(int i=k;i>0;i--)
        {
            int l=1,r=n/prime[i];
            if(r%2==0)r--;
            //cout<<prime[i]<<endl;
            //cout<<1;
            while(l<=r)
            {
                while(l*prime[i]<=n&&mark[l*prime[i]]==0)
                    l+=2;
                while(r>0&&mark[r*prime[i]]==0)
                    r-=2;
                if(r<=0||l*prime[i]>n)break;
                if(l==r)
                {
                    if(prime[i]*2<=n)
                    {
                        e.push_back(P(prime[i]*2,prime[i]*l));
                        mark[prime[i]*2]=0;
                        mark[prime[i]*l]=0;
                    }
                    break;
                }
                else if(l<r)
                {
                    e.push_back(P(prime[i]*r,prime[i]*l));
                    mark[prime[i]*r]=0;
                    mark[prime[i]*l]=0;
                }
            }
        }
        int l=2,r=n/2*2;
        while(l<r)
        {
            while(l<=n&&mark[l]==0)
                l+=2;
            while(r>0&&mark[r]==0)
                r-=2;
            if(l<r)
            {
                e.push_back(P(r,l));
                mark[r]=0;
                mark[l]=0;
            }
            if(l==r)break;
        }
        printf("%d\n",e.size());
        for(int i=0;i<e.size();i++)
            printf("%d %d\n",e[i].first,e[i].second);
    }
    return 0;
}