Codeforces 959D. Mahmoud and Ehab and another array construction task
题意
构造一个任意两个数都互质的序列，使其字典序大等于a序列且最小。
思路
其实这题乱搞就行了。用到了之前HDdalao教我的素因子分解方法，可以快速地对枚举的数进行检测。
我们维护一个当前已填的数的素因子集合以及一个大于1的自然数集合（考虑最坏情况，我们总可以都用素数来构造这个序列。由素数的密度可知，n/ln(n)要大于1e5，所以该自然数集合上限达到2e6即可）
从自然数集合中从小到大枚举当前要填的数，对其质因子分解，检测是否与前面的数互质，然后该数从自然数集合中删去。互质的话，其素因子加入素因子集合。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<string>
#include<vector>
#include<cmath>
#include<climits>
#include<functional>
#include<set>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<endl
#define fi firfac
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> V;
typedef set<int> S;
typedef queue<int> Q;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=2e6,INF=0x3f3f3f3f;
int minp[maxn],ans[maxn],cnt;
S fac,num;
void init()
{
for (int i=2;i<maxn;++i)
{
num.insert(i);
if (minp[i])
continue;
for (int j=i;j<maxn;j+=i)
{
if (!minp[j])
minp[j]=i;
}
}
}
bool check(int x)
{
int _x=x;
while (x!=1)
{
int p=minp[x];
if (fac.find(p)!=fac.end())
return 0;
while (x%p==0)
x/=p;
}
while (_x!=1)
{
int p=minp[_x];
fac.insert(p);
while (_x%p==0)
_x/=p;
}
return 1;
}
int main()
{
init();//de(minp[2]);
int n;
scanf("%d",&n);
S::iterator it;
bool f=0;
for (int i=0;i<n;++i)
{
int x;
scanf("%d",&x);
it = f? num.begin():num.lower_bound(x);
while (it!=num.end())
{
int t=*it;
if (check(t))
{
if (t>x)
f=1;
ans[cnt++]=t;
break;
}
it=num.erase(it);
}
}
for (int i=0;i<n;++i)
printf("%d ",ans[i]);
return 0;
}