D. Mahmoud and Ehab and another array construction task 因子分解模板
题意
给出一个原序列a 找出一个字典序大于a的序列b，使得任意 (i!=j),(gcd(a[i],a[j])==1)，现在要你找出这样的序列b,并且满足所有合法序列中输出字典序最小的那个
思路
维护一个set,set里面装所有当前可以取的合法元素，先把所有的数字放进set里面，因为要求字典序最小的序列b，并且b的字典序要大于a，当构造的b到当前位置截止时和a相同时，每次在set里面二分找第一个大于等于当前位置a的值，当不相同时，直接每次取set的最小的元素也就是首元素以满足构造的b字典序最小
因子分界模板 （听说是nlog(n),有空证一下）
void init(){
for(int i=2;i<maxn;i++){
if(!vis[i]){
vis[i]=1;
for(int j=i;j<maxn;j+=i){
vis[j]=1;
v[j].pb(i);
}
}
}
}
AC代码
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
using namespace std;
const int maxn=2e6+200;
bool vis[maxn+5];
set<int>s;
vector<int>v[maxn];
void init(){
for(int i=2;i<maxn;i++){
if(!vis[i]){
vis[i]=1;
for(int j=i;j<maxn;j+=i){
vis[j]=1;
v[j].pb(i);
}
}
s.insert(i);
}
}
bool vis2[maxn];
int main(){
int n;
init();
scanf("%d",&n);
int tmp;
int flag=1;
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
int now=*s.begin();
if(flag){
now=*s.lower_bound(tmp);
if(now!=tmp)flag=0;
}
//s.erase(now);
printf("%d ",now);
for(int &x:v[now]){
for(int j=x;j<maxn;j+=x){
if(!vis2[j]){
vis2[j]=1;
s.erase(j);
}
}
}
}
// for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}