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; }