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

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

##### 题目 #####

[题目链接][Link 1]  
给定一个 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;
    }

如果文章对你有帮助，请给我个赞吧：)

[Link 1]: https://ac.nowcoder.com/acm/contest/5669/H