D. Recover it!(素数筛) Codeforces Round #565 (Div. 3)
原题链接: https://codeforces.com/contest/1176/problem/D
测试样例
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;
}
上一篇: css重点知识和bug解决方法
下一篇: 为什么多喝水有益健康 喝水功效看这里
推荐阅读
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
D. Almost All Divisors(数学) Codeforces Round #560 (Div. 3)
-
D. Pair of Topics(构造+排序+优化处理)Codeforces Round #627 (Div. 3)
-
D. Cutting Out (二分查找) Codeforces Round #521 (Div. 3)
-
D. Recover it!(素数筛) Codeforces Round #565 (Div. 3)
-
Codeforces Round #261 (Div. 2) D. Pashmak and Parmida
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Codeforces Round #261 (Div. 2) D. Pashmak and Parmida