我要评论牛客暑假多校训练营（第四场）
H Harder Gcd Peoblem
题意：
给出N，在1～N所有数中，选出M对数字，并且每对数字满足gcd(a_i,b_i)>1，让M尽可能的大，且不能重复，输出最大的M以及这M对数字。
思路：
首先应考虑有哪些数不能参与匹配，分析可知，1与任何正数的gcd都为1，则1无匹配对象，再考虑质数，质数与它本身的倍数的gcd>1。所以，1和大于N/2的质数一定没有匹配对象。
则在此题中，首先筛选出N/2以内的素数，并记录在pri数组中：
//简单的埃氏筛法
void init()
{
for(int i=2;i<MAXN;i++){
if(!vis[i]){
pri[cnt++]=i;
for(int j=i*2;j<MAXN;j+=i)
vis[j]=1;
}
}
}
而我们所找出的素数和它所有的倍数是可以相互匹配的，则我们找出所有标记的质数的倍数，若一个数同时为多个素数的倍数，则只将其记录在较大的素数列表中，并记录下所找个数。
下图为当N=18时，所找出的质数与其倍数。
7 14
5 10 15
3 6 9 12 (15) 18
2 4 6 8 10 (12) 14 16 (18)
//记录下所有素数的倍数及其个数
//pos为找到小于N/2的最大质数的位置
for(int i=pos;i>=0;i--){
num=0;
for(int j=1;j*pri[i]<=N;j++)
if(!vis[pri[i]*j])
sum[num++]=pri[i]*j;
}
若该质数以及它的倍数总数为偶数，则将其俩俩任意匹配，若个数为奇数，则将该素数第二个数（也就是2倍）记录下来，而将其他所有的数两两匹配，最后在2的倍数处，将它们俩俩匹配，所得的个数即为最大值。
M对匹配分别为：
7的倍数为偶数则任意匹配
7 14
5的倍数为奇数，则留下第二个，其余的任意匹配
5 15
3的倍数为偶数，但是15已经被匹配过了，则将其排除
3 9
12 18
由于上述排除的数都为2的倍数，则在2的倍数处任意匹配
2 4
8 10
14 16
//两两匹配，将结果存在ans1[]和ans2[]中
if(num&1){
ans1[M]=sum[0]; ans2[M++]=sum[2];
vis[sum[0]]=1; vis[sum[2]]=1;
for(int i=3;i<num;i+=2
ans1[M]=sum[i]; ans2[M++]=sum[i+1];
vis[sum[i]]=1; vis[sum[i+1]]=1;
}
}
else{
for(int i=0;i<num;i+=2){
ans1[M]=sum[i];
ans2[M++]=sum[i+1];
vis[sum[i]]=1;
vis[sum[i+1]]=1;
}
}
最终完整代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
int T,N,cnt,num,M;
int pri[MAXN];
int vis[MAXN];
int ans1[MAXN],ans2[MAXN];
int sum[MAXN];
void init();
int main()
{
init();
scanf("%d",&T);
while(T--){
memset(vis,0,sizeof(vis));
M=0;
scanf("%d",&N);
int pos=upper_bound(pri,pri+cnt,N/2)-pri-1;
for(long i=pos;i>=0;--i){
num=0;
for(int j=1;j*pri[i]<=N;j++)
if(!vis[pri[i]*j])
sum[num++]=pri[i]*j;
if(num&1){
ans1[M]=sum[0]; ans2[M++]=sum[2];
vis[sum[0]]=1; vis[sum[2]]=1;
for(int i=3;i<num;i+=2){
ans1[M]=sum[i]; ans2[M++]=sum[i+1];
vis[sum[i]]=1; vis[sum[i+1]]=1;
}
}
else{
for(int i=0;i<num;i+=2){
ans1[M]=sum[i];
ans2[M++]=sum[i+1];
vis[sum[i]]=1;
vis[sum[i+1]]=1;
}
}
}
printf("%d\n",M);
for(int i=0;i<M;i++)
printf("%d %d\n",ans1[i],ans2[i]);
}
return 0;
}
void init()
{
for(int i=2;i<MAXN;i++){
if(!vis[i]){
pri[cnt++]=i;
for(int j=i*2;j<MAXN;j+=i)
vis[j]=1;
}
}
}
本文地址：https://blog.csdn.net/qq_44793348/article/details/108493496
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论