H. Haeder Gcd Problem

题意

集合A和B都是{1,2,.....,n}的子集，A∩B≠∅。问A和B最多有多少对数GCD(Ap，Bq)>1。

题解

所有gcd>1的两个数肯定是倍数关系，最小肯定是本身和2倍。越大的数能和他匹配的就会越少，为了简单，从大的数往小的数匹配。先用线性筛O(n)预处理出1-n之间的质数，然后找到小于n的质数最大，并且要有至少一个数可以和他配对。从这个质数开始往下计算，如果有偶数个可以和该质数配对的，那就直接记录下来；如果是奇数个，最简单的方法是将这个数的二倍放弃，剩下的记录下来。因为是2的倍数，肯定存在，并且方便计算。

代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

ll st[200100];
ll prime[200100];
ll cnt;

void Prime(ll n)
{
    cnt=0;
    for(ll i=2;i<=n;i++){
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]*i<=n;j++){
            st[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}

ll  quick(int a,int b)
{
    int res=1;
    while(b){
        if(b&1) res=(res*a);
        a=(a*a);
        b>>=1;
    }
    return res;
}

bool vis[200100];
vector<int>v[200100];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    Prime(200000);
    while(t--){
        memset(vis,0,sizeof(vis));
        int n;
        cin>>n;
        for(int i=0;i<=n;i++) v[i].clear();
        int k=cnt-1;
        for(int i=0;i<cnt;i++){
            if(prime[i]>n) {k=i-1;break;}
        }
        int ans=0;
        for(int i=k;i>=0;i--){
            int p=n/prime[i],x=0;
            for(int j=1;j<=n/prime[i];j++)
                if(!vis[prime[i]*j]) x++;
            if(x&1){
                int flag=0;
                if(n/prime[i]<2) continue;
                for(int j=1;j<=n/prime[i];j++){
                    if(!flag&&!vis[prime[i]*j]&&(prime[i]*j)%2==0) flag=1;     //删掉一个2的倍数
                    else if(!vis[prime[i]*j]) {
                        vis[prime[i]*j]=1;
                        v[i].push_back(prime[i]*j);
                    }
                }
            }
            else{
                for(int j=1;j<=n/prime[i];j++)
                    if(!vis[prime[i]*j]) {
                        vis[prime[i]*j]=1;
                        v[i].push_back(prime[i]*j);
                    }
            }
        }
        for(int i=0;i<=k;i++){
            ans+=v[i].size()/2;
        }
        cout<<ans<<endl;
        for(int i=0;i<=k;i++){
            for(int j=1;j<v[i].size();j+=2){
                cout<<v[i][j-1]<<' '<<v[i][j]<<endl;
            }
        }
    }
    return 0;
}