数论 + 贪心 - Harder Gcd Problem - 2020牛客暑期多校训练营（第四场）+ Jzzhu and Apples

数论 + 贪心 - Harder Gcd Problem - 2020牛客暑期多校训练营（第四场）+ Jzzhu and Apples - CF 449C

题意：

$T组测试数据，$

$每组包括一个整数n，$

$要求从1到n的排列：$ {1,2,…,n} $\ 中，选择出两个子集A和B。$

$满足：|A|=|B|=m且A∩B=\phi。$

$\qquad\ \ \ 且对于任意的元素a_i∈A，b_i∈B，gcd(a_i,b_i)>1，1≤i≤m。$

$求出m的最大值，并输出长度为m的两个集合A和B。$

输入描述：

$首行一个正整数T，表示测试数据的数量$

$接下来T行，每行输入正整数n(4≤n≤2×10 ^5)。$

输出描述：

$首行一个正整数sum，表示m的最大值。$

$接着输出sum行数，第i行为a_i和b_i，1≤i≤m。$

示例1
输入

2
4
10

输出

分析:

$出CF原题是我没想到的(出题人是不是有点偷懒...$

原题链接：《Jzzhu and Apples》

$本题只是改成了T组测试数据。$

$分析一下贪心策略吧，下午做的时候是想得很接近了，写到一半放弃(蔡。$

$首先应该能够发现，有公约数的数之间可以任意匹配，特殊的是质数，$

$对于质数P，若P×2>n，则无需考虑这个质数。$

$对于满足2×P≤n的质数，可以用P的倍数与之配对，这样才能保证尽量多的数被使用了。$

$以因子P为划分依据，将P的倍数都存储到同一个集合中去，相同集合中任意两个数均能形成一对匹配。$

$输出时，我们将同一集合中的元素两两输出即可。$

注意：

$①、要从大到小枚举质数P。$

$\qquad理由：假设有P_1<P_2，P_1所在集合中S_{P_1}，P_2所在集合S_{P_2}。$

$\qquad其中S_{P_1}=$ { $P_1,2P_1,...,\lfloor\frac{n}{P_1}\rfloor P_1$ }， $S_{P_2}=$ { $P_2,2P_2,...,\lfloor\frac{n}{P_2}\rfloor P_2$ }，

$\qquad则必有|S_{P_1}|>|S_{P_2}|，若存在S_{P_1}∩S_{P_2}=kP_1，此时我们让kP_1与S_{P_2}中的元素匹配才是最优的。$

$②、当集合中的元素大于1且为奇数时，我们就将2×P保留下来，将剩下的数两两匹配。$

$\qquad因为，2是最小的质数，可操作性更强，即集合S_2中的元素数量最多。$

$③、最后要将所有未被匹配的偶数累加上，即因子为2(最小的质数)的未被匹配的数的集合。$

疑问：这样的做法能够保证考虑过1~n中的所有数了吗？

$答案是肯定的，参考埃式筛法。$

$因为每个质数都被考虑到了，且每个质数的倍数也都被对应考虑到了。$

另外：

$输出时下标可从1开始两两输出，可以直接过滤掉数组中的元素数量只有1个的不合法情况。$

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>using namespace std;const int N=2e5+10;int primes[N],cnt;
bool st[N];
bool vis[N];void get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]*i<=n;j++){st[primes[j]*i]=true;if(i%primes[j]==0) break;}}
}int main()
{get_prime(2e5);int T,n;cin>>T;while(T--){vector<int> res[N];scanf("%d",&n);for(int i=0;i<=n;i++) vis[i]=false;int sum=0;for(int i=cnt-1;i>0;i--){int p=primes[i];for(int j=p;j<=n;j+=p)if(!vis[j]) {res[i].push_back(j);vis[j]=true;}int S=res[i].size();if(S>1 && S&1) {int tmp=res[i][1];res[i].erase(res[i].begin()+1);vis[2*p]=false;S--;}sum+=S/2;}for(int i=2;i<=n;i+=2)if(!vis[i])res[0].push_back(i);sum+=res[0].size()/2;printf("%d\n",sum);for(int i=0;i<cnt;i++){int t=res[i].size();for(int j=1;j<t;j+=2) printf("%d %d\n",res[i][j-1],res[i][j]);}}return 0;
}