题目链接:https://ac.nowcoder.com/acm/contest/5669/H

在这里插入图片描述在这里插入图片描述

题意

给你一个大小为n的序列{1,2,...,n},要求每次从序列中取出两个不互质的数构成一对,并且每个数只能被取一次。
现在要求最多能取多少对,并输出取数方案(可能不唯一)。

思路

n以具体的数字为例,方便找到规律,理顺思路。

比如,现在n=26,最小素因子是2,为了避免重复,我们先得到小于等于n/2的素数:2,3,5,7,13。

求这些素数的倍数(小于等于n),列出表格方便观察,如下:
|p| p2 | p3 | p4 | p5 | p6 | p7 | p8 | p9 | p10 |p11 |p12 |p13 |
|--|--|--|--|--|--|--|--|--|--|--|--|--|
| 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |22 |24 |26 |
| 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 |
| 5 | 10 | 15 | 20 | 25 |
| 7 | 14 | 21 |
| 13 | 26 |

不难发现,同一行或者同一列(列>1)的任意两个数字都不互质,可以任意配对。但是在表格中数字会有重复,由于每个数字只能用一次,所以我们要想一个贪心策略来选数。观察上表,可以发现第2列的所有数字都会在第1行再次出现,第2列到第13列中的数字也可能会多次出现,而只有第1列的所有数字只会出现一次。

考虑每一行之间的数字互相配对的方案。
(1)由于第1行(都是偶数)比较特殊,不妨从第2行开始配对,也就是把偶数留下来最后配对。
(2)由于第1列(都是素数,只出现一次)和第2列(都是偶数,并且在第1行再次出现)比较特殊,所以每行的配对都先从第3列开始。
①如果第3列后没被用过的数字个数为奇数个,则将最后一个可行数字与第1列的数字配对。
原因:这样就会留下第2列的数字没配对,没关系,它们都是偶数,那么就一定在第1行出现,只要最后在第1行配对所有没被用过的偶数即可。
②如果第3列后没被用过的数字个数为偶数个,则将第2列的数字与第1列的数字配对。
原因:这里就体现出了贪心策略,因为第2列的数字都在第1行再次出现,也就是说它们可以和第1行的任意数字配对,但是如果那样配对就会消耗第1行的数字,总配对数显然会少于第2列与第1列数字进行配对的方案。应该要留更多的机会让第1行数字互相配对。
(3)最后配对第1行的数字,即配对所有还没被用过的偶数。

n=26时,输出如下:

11
9 12
15 18
21 24
3 6
20 25
5 10
7 14
11 22
13 26
2 4
8 16

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
bool isprime[N+10],vis[N+10];
int T,n,cnt,prime[N+10];
vector<int>ans;
void get_prime() // 素数筛打表
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(isprime[i])prime[++cnt]=i;
        for(int j=1;i*prime[j]<=N;j++)
        {
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    cin>>T;
    while(T--)
    {
        cin>>n;
        int mx=n/2;
        ans.clear();
        memset(vis,0,sizeof(vis));
        for(int i=2;prime[i]<=mx;i++) // 从第2个素数,也就是prime[2]=3开始枚举
        {
            int p=prime[i];
            int tot=0;
            for(int j=3;j*p<=n;j++) // 素因子p乘以j
            {
                int x=j*p;
                if(!vis[x])
                {
                    vis[x]=1;
                    ans.push_back(x);
                    tot++;
                }
            }
            if(tot&1) //第3列后没被用过的数字个数为奇数个,则将最后一个可行数字与第1列的数字配对
            {
                vis[p]=1;
                ans.push_back(p);
            }
            else //第3列后没被用过的数字个数为偶数个,则将第2列的数字与第1列的数字配对
            {
                vis[p]=1;
                vis[2*p]=1;
                ans.push_back(p);
                ans.push_back(2*p);
            }
        }
        int tot=0;
        for(int i=1;i<=mx;i++) //最后处理所有偶数之间的配对
        {
            int x=i*2;
            if(!vis[x])
            {
                vis[x]=1;
                ans.push_back(x);
                tot++;
            }
        }
        if(tot&1)ans.pop_back(); //多余了一个,去掉
        int sz=ans.size();
        printf("%d\n",sz/2);
        for(int i=0;i<sz;i+=2)
            printf("%d %d\n",ans[i],ans[i+1]);
    }
    return 0;
}