当前位置： 移动技术网 > IT编程>开发语言>.net > 2020牛客暑期多校训练营（第四场）H.Harder Gcd Problem

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

2020年07月27日  | 移动技术网IT编程  | 我要评论

H.Harder Gcd Problem

题目链接-H.Harder Gcd Problem
在这里插入图片描述
在这里插入图片描述
题目大意
集合AA和BB都是集合{1,2,.....,n}\{1,2,.....,n\}的子集，且A∩B≠∅A∩B≠∅。问AA和BB最多有多少对数满足gcd(Ai，Bj)>1gcd(A_i，B_j)>1

解题思路

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

附上代码

//#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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网