H题题解
Ancient Distance
https://ac.nowcoder.com/acm/contest/5669/A
H题题解
题意：
给出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;
}
查看5道真题和解析
