H题题解_牛客博客

H题题解

先骗个访问量：https://blog.csdn.net/weixin_45539557/article/details/107468989

题意：

给出1-n的数字，让选择m对数字，让gcd(a_i,b_i)>1，让m尽可能大，并且输出这m对对应的数字。

思路：
首先m我们很容易猜测到，应该是（n-1-所有大于n/2的质数）/2,因为大于n/2的质数和1不可能和任何数匹配，剩下的数我们猜测一定能做到两两匹配。
下面我们给出构造方式
我们筛出<=n/2每个质数及其倍数
举例，n=18如下图

那构造方式就很明显了
我们从表中从下往上构造
对于质数t及其倍数构成若干个集合
如果当前集合的个数是偶数个，那么里面任意匹配
如果是奇数个，我们保留2*t，这样就可以最大化的留下所有数，剩下偶数个随便匹配，当然要标记掉匹配的数字，最后我们剩下的全是含有2的质因子的数，直接任意匹配
我们可以发现，这样构造本质是对我所说的最大的m的证明，这个表中包含除了1以及大于n/2的质数，最坏情况就是最后2的集合中是奇数，剩下一个，否则表中全部数都能匹配完成，所以这个必然是最优匹配

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int prime[maxn/20],cnt=0,ans1[maxn/2],ans2[maxn/2],sum[maxn/2];
bool v[maxn/2],v1[maxn];

void init(int maxm){ 
    v[1]=1;
    for(int i=2;i<=maxm;++i){ 
        if(!v[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=maxm;++j){ 
            v[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
   init(100000);
   int t,n;
   scanf("%d",&t);
   while(t--){ 
       scanf("%d",&n);
       for(int i=1;i<=n;++i)
           v1[i]=0;
       int k=n/2,m=0;
       int f=upper_bound(prime+1,prime+1+min(cnt,k),k)-prime-1;
       for(int i=f;i>=1;--i){ 
            int num=0;
            sum[++num]=prime[i];
            for(int j=2;prime[i]*j<=n;++j){ 
                int h=prime[i]*j;
                if(!v1[h])
                    sum[++num]=h;
            }
            if(num&1){ 
                ans1[++m]=sum[1];ans2[m]=sum[3];
                v1[sum[1]]=1;v1[sum[3]]=1;
                for(int i=4;i<=num;i+=2)
                    ans1[++m]=sum[i],ans2[m]=sum[i+1],v1[sum[i]]=1,v1[sum[i+1]]=1;
            }
            else{ 
                for(int i=1;i<=num;i+=2)
                    ans1[++m]=sum[i],ans2[m]=sum[i+1],v1[sum[i]]=1,v1[sum[i+1]]=1;
            }
       }
       printf("%d\n",m);
       for(int i=1;i<=m;++i)
           printf("%d %d\n",ans1[i],ans2[i]);
   } 
   return 0; 
}