题面:
题意:
有 1...n共n个数字。
从中选出两个子集A、B,其中 A ∩ B = 空。集合A和集合B的大小均为m。
我们对于A集合和B集合中的元素按照某一顺序放置后,可以使得任意的 gcd(ai,bi)>1
简化:
把 1~N 的数选尽量多的组,使得每组 gcd 大于 1。
输出任意一种方案
题解:
考虑m最大能取到多大,除了大于 n/2 的质数和 1,其余的数是可以均分到两个集合中的(如果剩余的数是奇数,扔掉一个就好啦)。
考虑如何构造一个可行解。
现在我们已经将大于 n/2 的质数和 1从序列中去除了。
我们按照每个数的最大质因子分类,最大质因子相同的数放在同一类中,那么某一类一定是
p,2p,3p...等等,可以证明最终一定可以划分为若个类。
这里的p的系数不一定连续,例如 p=3时,那么是 p,2p,3p,4p,6p,8p
如果某个类中有偶数个数,那么他们两两匹配即可。
如果某个类中有奇数个数,那么就将 2p 留出来,放置最大质因子为2的集合中,剩下的两两匹配。
最终最大质因子为2的集合中的数一定都能被2整除。
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int up=100100;
int prime[maxn],maxx[maxn],cnt;
bool ha[maxn];
vector<int>vc[maxn];
vector<pair<int,int> >ans;
void Prime(void)
{
ha[1]=true;
maxx[1]=0;
for(int i=2;i<maxn;i++)
{
if(!ha[i])
{
prime[++cnt]=i;
maxx[i]=cnt;
}
for(int j=1;j<=cnt&&prime[j]*i<maxn;j++)
{
ha[i*prime[j]]=true;
maxx[i*prime[j]]=max(maxx[i],j);
if(i%prime[j]==0) break;
}
}
}
int main(void)
{
int t;
scanf("%d",&t);
Prime();
while(t--)
{
int n;
scanf("%d",&n);
vc[1].clear();
int ma=0;
for(int i=2;i<=n;i++)
{
vc[i].clear();
if(i>n/2&&ha[i]==false) continue;
vc[maxx[i]].pb(i);
ma=max(ma,maxx[i]);
}
ans.clear();
for(int i=ma;i>=2;i--)
{
if(vc[i].size()==0) continue;
if(vc[i].size()%2==0)
{
for(int j=0;j<vc[i].size();j+=2)
ans.pb(pr(vc[i][j],vc[i][j+1]));
}
else
{
ans.pb(pr(vc[i][0],vc[i][2]));
vc[1].pb(vc[i][1]);
for(int j=3;j<vc[i].size();j+=2)
ans.pb(pr(vc[i][j],vc[i][j+1]));
}
}
//2
for(int i=0;i+1<vc[1].size();i+=2)
ans.pb(pr(vc[1][i],vc[1][i+1]));
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
printf("%d %d\n",ans[i].first,ans[i].second);
}
return 0;
}