https://ac.nowcoder.com/acm/contest/5669
F Finding the Order（贪心）
题意：
给出1-n的数字，让进行一一配对，使得每一对gcd(a_i,b_i)>1，要求配对数目尽量多，并且输出这m对对应的数字。
思路：
要使得m尽量大，m就要尽量靠近k=（n-1-所有大于n/2的质数）/2。因为大于n/2的质数都不可能配对，1也不可能有配对。
如何做到靠近这个数字呢？
把小于等于n/2的质数罗列出，一个占据一排，并且在代表每个质数的那一排后面罗列出它的小于n的倍数。
比如当n==18：
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18
5 10 15
7 14
然后我们从大到小配对，同一排自由配对。比如将7与14配对。
但是我们很快发现5那一排有三个数字，不能两两配对。那就把10预留下来。因为最后进行配对的质数是2，10是2的倍数，可以留尽量多的数字在最后2那一行的配对中。
这样是最优的，是最可能接近k的。
那么5和15配对，留下10。然后观察3的那一行。15已经配好对了，划掉他。那么我们还剩下3 6 9 12 18，又是奇数。那就把6预留，剩下的数字配对。
最后在2的那一行，只剩下2 4 6 8 10 14 16。如果这一排的数字是偶数，那么我们的m就==k，得到最优解。但是现在是奇数，那就遗憾一点，得到m=k-1，但仍然是最优解了。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; int prime[maxn/2],vis[maxn/2],vis2[maxn]; int cnt; void init(){ cnt=0; for(int i=2;i<=maxn/2;i++){ if(vis2[i]==false) prime[++cnt]=i; for(int j=1;j<=cnt&&i*prime[j]<=maxn/2;j++){ vis2[i*prime[j]]=true; if(i%prime[j]==0) break; } } } int main(){ int t; scanf("%d",&t); init(); while(t--){ int n; scanf("%d",&n); vector<int>v1,v2,v3; int k=n/2; memset(vis2,0,sizeof(vis2)); int pos=upper_bound(prime+1,prime+1+min(cnt,k),k)-prime-1; for(int i=pos;i>=2;i--){ int ccnt=0; for(int j=1;j*prime[i]<=n;j++){ if(vis2[j*prime[i]]) continue; else ccnt++; } if(ccnt&1){ int tmp=1; for(int j=1;j*prime[i]<=n;j++){ if(vis2[j*prime[i]]) continue; if(j==2) continue; vis2[j*prime[i]]=1; if(tmp) v1.push_back(j*prime[i]); else v2.push_back(j*prime[i]); tmp^=1; } v3.push_back(2*prime[i]); }else{ int tmp=1; for(int j=1;j*prime[i]<=n;j++){ if(vis2[j*prime[i]]) continue; vis2[j*prime[i]]=1; if(tmp) v1.push_back(j*prime[i]); else v2.push_back(j*prime[i]); tmp^=1; } } } int ccnt=0;
//最后检查2的倍数们。其实这些过程可以合并到上面去。 for(int j=1;j*2<=n;j++){ if(vis2[j*2]) continue; else ccnt++; } int tmp=1; if(ccnt&1){ for(int j=2;j*2<=n;j++){ if(vis2[j*2]) continue; if(tmp) v1.push_back(j*2); else v2.push_back(j*2); tmp^=1; } }else{ for(int j=1;j*2<=n;j++){ if(vis2[j*2]) continue; if(tmp) v1.push_back(j*2); else v2.push_back(j*2); tmp^=1; } } int ans=v1.size(); printf("%d ",ans); for(int i=0;i<ans;i++){ printf("%d %d ",v1[i],v2[i]); } } }