基础算法题——Harder Gcd Problem（数论、思维）-蒲公英云

基础算法题——Harder Gcd Problem（数论、思维）

你的名字 2023-03-01 09:40 18阅读 0赞

题目

题目链接
给定一个 n，将 2~n 内的数进行一对一匹配，每个数仅能利用一次。
假设 a 与 b 匹配，则 gcd(a,b) != 1。现求 2~n 内最大匹配数量，并输出匹配数对。

输入
T代表输入组数。
下面T行，每一行一个数字n。

输出
输出最大匹配数量 m
下面m行，每一行一对匹配数对

示例1
输入样例
2
4
10
输出样例
1
2 4
4
3 9
5 10
8 2
4 6

解题思路

数论知识：合数一定能够通过质数相乘得到。

总体思路

将 n 以内的质数尽量匹配。
通过质数将合数尽量匹配。

逐步分析
①、筛选出质数存储在数组 p 中。

②、在 p 中寻找到最大小于 n/2 的质数下标 pos。

③、从大到小枚举 p 数组中下标 pos~0 的数。
（质数越大越难匹配成功，将难匹配成功的质数先匹配）

思考

我们知道一定存在 2 * p[i] <= n ，但我们并不知道，在 n 内是 p[i] 的倍数数量 x 是多少？
（ps：假设p[i]=3，那么在10内 x = 3，分别为3，6，9）

为了方便数字匹配，我们要提前保留一个2 * p[i]。若 x 为偶数，那么则将 2 * p[i] 这个数加入匹配，否则则舍弃 2 * p[i]。

④、枚举完 n/2 以内所有质数，在合数一定能够通过质数相乘得到的条件下，直接输出结果。

实现代码

#include<bits/stdc++.h>
#define ll long long;
using namespace std;
const int N=2e5+5;
int p[N], ans[N], tot, cnt;
bool judge[N], vis[N];
void init(){ 
    int n=2e5;
    for(int i=2;i<=n;i++){ 
        if(judge[i]==false){ 
            p[cnt++]=i;        //存储质数 
            for(int j=2; j*i<=n;j++){ 
                judge[i*j] = true;
            }
        }
    }
}
int main(){ 
    int t;
    init();
    scanf("%d",&t);
    while(t--){ 
        int n;
        tot=0;
        scanf("%d",&n);
        memset(vis, false, sizeof(vis));
        //找到最大符合条件的质数下标 
        int pos = upper_bound(p, p+cnt, n/2) - p - 1;
        for(int i=pos; i>=0; i--){     
            //将 p[i] 的倍数的数进行匹配 
            for(int j=p[i]; j<=n; j+=p[i]){ 
                //若 j 已经匹配过则跳过 或 j==2*p[i] 
                if(vis[j]==true||j==p[i]*2){ 
                    continue;
                }
                ans[++tot] = j;
                vis[j] = true;
            }
            //若p[i]倍数匹配完，tot为奇数，还差一个配对
            //对应的数直接取2*p[i] 
            if(tot%2){ 
                vis[p[i]*2] = true;
                ans[++tot] = p[i]*2;
            }
        }
        printf("%d\n",tot/2);
        for(int i=1;i<=tot;i+=2){ 
            printf("%d %d\n", ans[i], ans[i+1]);
        }
    }
    return 0;
}