欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

D. Recover it!(素数筛) Codeforces Round #565 (Div. 3)

程序员文章站 2022-06-04 18:44:04
...

原题链接: https://codeforces.com/contest/1176/problem/D

D. Recover it!(素数筛) Codeforces Round #565 (Div. 3)
测试样例

input
3
3 5 2 3 2 4
output
3 4 2
input
1
2750131 199999
output
199999
input
1
3 6
output
6

题意: 有一个长度为 n n n的整数序列 a a a,现在构造一个整数序列 b b b,构造方法为先复制 a a a,再对每个 a i a_i ai进行如下操作:

  • a i a_i ai为素数,则将素数表中第 a i a_i ai的素数加到整数序列 b b b中。素数表为 ( 2 , 3 , 5 , 7..... ) (2,3,5,7.....) (2,3,5,7.....)
  • a i a_i ai不为素数,则将不是 a i a_i ai本身的最大因子加入到整数序列中。

完成操作后,将整数序列 b b b混乱排序。
易知构造完成的整数序列 b b b长度为 2 × n 2\times n 2×n。系统给出这个序列 b b b,要求你恢复序列 a a a

解题思路: 这道题真的出得特别好,也有一定的难度,若没看懂是真的不知道从何处理。我们来看,给定的序列有素数和非素数,每个元素对应一个。我们每找到一个那么就可以消掉一个,那么我们该如何去找?序列中的素数可能由素数产生也有可能由非素数产生,所以我们一开始绝对不能处理素数,再看非素数,我们从大到小看,最大的非素数一定是原序列中的,因为没别的可以产生它。那么它的最大因子也可以找到,那么思路就有了,我们从大到小看,依次遍历非素数,消掉对应的值。 最后剩下的值一定都是素数了,这个时候我们发现是小素数产生大素数(这里自行体会,可以画个素数表感受一下。),所以我们从小到大遍历依次可以找到对应的元素值。 故此题可解。注意提前打表。这样时间复杂度会小很多,我300多ms过的。

AC代码

/*
*邮箱:aaa@qq.com
*blog:https://me.csdn.net/hzf0701
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a为初始值,n为界限值,递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量, a为初始值,n为界限值,递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 2e5+3;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线,以上为自定义代码模板***************************************//

vector<int> primers;//素数表
bool isprimer[2750132];//位置素数表。
int cnt[2750132];//统计出现次数
int b[maxn<<1];
int n;
int big_factor(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			return n/i;
		}
	}
}
void init(){
	memset(isprimer,true,sizeof(isprimer));
	primers.pb(0);//占位作用
	for(int i=2;i<=2750131;i++){
		if(isprimer[i]){
			primers.pb(i);
		}
		if((ll)i*i<=2750131){
			for(int j=i*i;j<=2750131;j+=i){
				isprimer[j]=false;
			}
		}
	}
}
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	init();
	while(cin>>n){
		vector<int> result;
		memset(cnt,0,sizeof(cnt));
		rep(i,1,2*n){
			cin>>b[i];
			cnt[b[i]]++;
		}
		sort(b+1,b+1+2*n);
		per(i,2*n,1){
			if(cnt[b[i]]&&!isprimer[b[i]]){
				result.pb(b[i]);
				cnt[b[i]]--;
				cnt[big_factor(b[i])]--;
			}
		}
		rep(i,1,2*n){
			if(cnt[b[i]]&&isprimer[b[i]]){
				cnt[b[i]]--;
				cnt[primers[b[i]]]--;
				result.pb(b[i]);
			}
		}
		int len=result.size();
		rep(i,0,len-1){
			cout<<result[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}