题目大意

给出一个集合的大小n，构造两个一样的集合A和B，分别包含{1,2,...,n}。
对两个集合中的不同数两两组合，每一对gcd(Api,Bqi)>1，求最多有多少对。

解题思路


思路一：
首先应该考虑有那些数不能参与匹配。显而易见1和大于n/2的素数一定没有匹配对象，可以直接忽略。
接下来考虑剩下的素数，倒序枚举每个素数p，找出所有未匹配的p的倍数，并且记下总数。 如果总数是偶数，那么这些数就可以完美两两匹配；否则留下2p（2的倍数最为常用，可以用于应对最后剩下的数），匹配其余的数。
最后只会留下一堆偶数，而它们两两都可以随意匹配。

AC代码 


#include<bits/stdc++.h>
using namespace std;
long long a[200010],b[200010];
int main()
{
    int t,n,x,ans,i,j;
    for(i=2;i<=200000;i++)
        if(b[i]==0)
            for(j=2*i;j<=200000;j+=i) b[j]=1;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        for(i=2;i<=n;i++) a[i]=0;
        for(i=n;i>=2;i--)
            if(!b[i])
            {
                x=i;
                for(j=n/i*i;j>i;j-=i)
                {
                    if(a[j]) continue;
                    if(x==0) x=j;
                    else ans++,a[x]=j,a[j]=x,x=0;
                }
            }
        printf("%d\n",ans);
        for(i=2;i<=n;i++)
            if(a[i]>i) printf("%d %d\n",i,a[i]);
    }
}