2020牛客暑期多校训练营（第四场）H.Harder Gcd Problem

H.Harder Gcd Problem

题目链接-H.Harder Gcd Problem


题目大意
集合$A$和$B$都是集合$\{1,2,.....,n\}$的子集，且$A∩B≠∅$。问$A$和$B$最多有多少对数满足$gcd(A_i，B_j)>1$

解题思路

• 所有$gcd>1$的两个数肯定是倍数关系，最小也就是$2$倍，所以大于$n/2$的质数肯定没法匹配，直接忽略就行
• 我们可以用素数筛预处理素数，越大的数能和他匹配的就会越少，所以我们从大的数往小的数匹配，找出所有未匹配的质数$p$的倍数，并且记下总数
• 如果所有未匹配的质数$p$的倍数的总数是偶数，那么这些数就可以两两匹配，否则就留下$2p$（因为我们要优先把大的数匹配完，所以留下$2p$）
• 最后剩下的数就全是偶数了，两两随机匹配即可
• 具体操作见代码

附上代码

//#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[N],b[N];
void pre(){
	for(int i=2;i<=N;i++){
		if(!b[i]){
			for(int j=2*i;j<=N;j+=i)
				b[j]=1;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int t;
	pre();
	cin>>t;
	while(t--){
		int n,ans=0;
		cin>>n;
		for(int i=2;i<=n;i++)
			a[i]=0;
		for(int i=n/2;i>=2;i--){
			if(!b[i]){
				int x=i;
				for(int 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;
					}
				}
			}
		}
		cout<<ans<<endl;
		for(int i=2;i<=n;i++)
			if(a[i]>i)
				cout<<i<<" "<<a[i]<<endl;
	}
	return 0;
}

本文地址：https://blog.csdn.net/Fiveneves/article/details/107573026