当前位置: 代码迷 >> 综合 >> 数论 + 贪心 - Harder Gcd Problem - 2020牛客暑期多校训练营(第四场)+ Jzzhu and Apples - CF 449C
  详细解决方案

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

热度:85   发布时间:2024-01-30 17:59:08.0

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

题意:

T T组测试数据,

n 每组包括一个整数n,

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

A = B = m A B = ? 满足:|A|=|B|=m且A∩B=\phi。

    a i A b i B g c d ( a i , b i ) > 1 1 i m \qquad\ \ \ 且对于任意的元素a_i∈A,b_i∈B,gcd(a_i,b_i)>1,1≤i≤m。

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

输入描述:

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

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

输出描述:

s u m m 首行一个正整数sum,表示m的最大值。

s u m i a i b i 1 i m 接着输出sum行数,第i行为a_i和b_i,1≤i≤m。

示例1
输入

2
4
10

输出

1
2 4
4
3 9
5 10
8 2
4 6

分析:

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

原题链接:《Jzzhu and Apples》

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

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

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

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

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

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

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

注意:

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

P 1 < P 2 P 1 S P 1 P 2 S P 2 \qquad理由:假设有P_1<P_2,P_1所在集合中S_{P_1},P_2所在集合S_{P_2}。

S P 1 = \qquad其中S_{P_1}= { P 1 , 2 P 1 , . . . , ? n P 1 ? P 1 P_1,2P_1,...,\lfloor\frac{n}{P_1}\rfloor P_1 }, S P 2 = S_{P_2}= { P 2 , 2 P 2 , . . . , ? n P 2 ? P 2 P_2,2P_2,...,\lfloor\frac{n}{P_2}\rfloor P_2 },

S P 1 > S P 2 S P 1 S P 2 = k P 1 k P 1 S 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 ②、当集合中的元素大于1且为奇数时,我们就将2×P保留下来,将剩下的数两两匹配。

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

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

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

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

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

另外:

1 1 输出时下标可从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;
}
  相关解决方案