Codeforces #473 Div2 D. Mahmoud and Ehab and another array construction task

割と好調だった回。
http://codeforces.com/contest/959/problem/D

問題

整数列A[i]に対し、以下を満たす整数列のうち辞書順最小のものを答えよ。

• B[i]は辞書順でA[i]以上
• B[i]は2以上
• Bの２つの要素は互いに素

解法

A[i]以上で辞書順最小のものを求めるので、先頭から順にB[i]=A[i]を維持できるか見ていこう。
A[0]から順に素因数分解し、出てきた素因数を覚えておく。

A[i]に含まれる素因数がA[0]～A[i-1]の素因数として登場すると、B[i]＞A[i]とせざるを得なくなる。
その場合、B[i]をA[i]から素因数が重複しなくなるまでインクリメントしていこう。
一旦B[i]＞A[i]となるiが出てきたら、それ以降は辞書順最小となるのがよい。
よって以降はB[i]として未出の素数を小さい順に割り当てよう。

int N;
int A[101010];
int B[101010];
int did[3000000];
const int prime_max = 3000000;
int NP,prime[300000],divp[prime_max];
map<int,int> M;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

set<int> enumpr(ll n) {
	set<int> V;
	
	while(divp[n]>1) {
		V.insert(divp[n]);
		n/=divp[n];
	}
	if(n>1) V.insert(n);
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	int ng=0;
	int prev=0;
	FOR(i,N) {
		if(ng==0) {
			set<int> V=enumpr(A[i]);
			FORR(v,V) if(did[v]) ng=1;
			
			if(ng==0) {
				B[i]=A[i];
				FORR(v,V) did[v]=1;
			}
			else {
				ng=1;
				B[i]=A[i]+1;
				while(1) {
					set<int> V=enumpr(B[i]);
					int ok=1;
					FORR(v,V) if(did[v]) ok=0;
					if(ok==0) {
						B[i]++;
						continue;
					}
					FORR(v,V) did[v]=1;
					break;
				}
			}
		}
		else {
			while(did[prime[prev]]==1) prev++;
			B[i]=prime[prev];
			did[prime[prev]]=1;
		}
		cout<<B[i]<<" ";
	}
	cout<<endl;
}

まとめ

軽くひっかけがあって適度な難易度の問題。