[nowcoder5669H]Harder Gcd Problem

题目相当于问1-n中最多能选出多少对不互素无交集的二元组，并要求方案

构造：将所有数放入其最小质因子对应的集合，若素数p所对应的集合元素个数为奇数且$p\ne 2$且$2p\le n$，那么就将$2p$从2对应的集合移到p对应的集合，最终每一个集合中选择$\frac{|S|}{2}$（下取整）对即可

关于这一构造的正确性证明：

1.合法性：素数p所对应的集合中的每一个元素都有公素因子p，因此两两不互素；同时每一个数最多只存在于一个集合，因此不会重复

2.最优性：首先对于$2p>n$的素数p和1都无法参与答案，那么剩余元素的最小质因子一定在$[2,\frac{n}{2}]$中，而通过构造中的调整一定可以使得$(2,\frac{n}{2}]$中的集合元素个数都为偶数，因此最多剩下1个数，不存在更多的匹配

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 vector<int>v,ans[N];

 5 int E,t,n,p[N],mn[N],vis[N],bl[N];

 6 int main(){

 7     for(int i=2;i<N-4;i++){

 8         if (!vis[i]){

 9             p[++p[0]]=i;

10             mn[i]=i;

11         }

12         for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){

13             vis[i*p[j]]=1;

14             mn[i*p[j]]=p[j];

15             if (i%p[j]==0)break;

16         }

17     }

18     scanf("%d",&t);

19     while (t--){

20         scanf("%d",&n);

21         for(int i=1;i<=n;i++)vis[i]=0;

22         for(int i=2;i<=n;i++){

23             vis[mn[i]]++;

24             bl[i]=mn[i];

25         }

26         for(int i=1;(i<=p[0])&&(p[i]<=n);i++)

27             if ((vis[p[i]]&1)&&(p[i]<=n/2))bl[2*p[i]]=p[i];

28         for(int i=1;i<=n;i++)ans[i].clear();

29         for(int i=2;i<=n;i++)ans[bl[i]].push_back(i);

30         int sum=0;

31         for(int i=2;i<=n;i++)sum+=ans[i].size()/2;

32         printf("%d\n",sum);

33         for(int i=1;(i<=p[0])&&(p[i]<=n);i++)

34             for(int j=0;j+1<ans[p[i]].size();j+=2)printf("%d %d\n",ans[p[i]][j],ans[p[i]][j+1]);

35     }

36 }

巴特西

[nowcoder5669H]Harder Gcd Problem

最新文章

热门文章