Codeforces 959D D. Mahmoud and Ehab and another array construction task_综合

一个老学长让我做的一个好题，刚开始题意没读对，想了好长时间，没想法，后来由一个女生给我讲了一下，我才有了想法，虽然T了N遍，总算过了，下面给大家分享一下。

Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:

b is lexicographically greater than or equal to a.
bi?≥?2.
b is pairwise coprime: for every 1?≤?i?<?j?≤?n, bi and bj are coprime, i. e. GCD(bi,?bj)?=?1, where GCD(w,?z) is the greatest common divisor of w and z.

Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array x is lexicographically greater than an array y if there exists an index i such than xi?>?yi and xj?=?yj for all 1?≤?j?<?i. An array x is equal to an array y if xi?=?yi for all 1?≤?i?≤?n.

Input

The first line contains an integer n (1?≤?n?≤?105), the number of elements in a and b.

The second line contains n integers a1, a2, ..., an (2?≤?ai?≤?105), the elements of a.

Output

Output n space-separated integers, the i-th of them representing bi.

Note

Note that in the second sample, the array is already pairwise coprime so we printed it.

大致意思是，给出你n个数，然后让你改变这个序列，找出满足要求的另外一个序列。

要求是每个数两两之间互质，然后要求新的序列字典序要大于等于第一个序列，但是要求找出字典序最小。

思路：每次输入一个数，你就去分解这个数，然后把分解出来它们的因子的倍数标记，这儿要优化一下，比如标记过得因子的倍数就不用再标记了。如果你输入的这个数被标记过，那么你是不是要修改这个数，而且题目要求字典序要大于等于第一个序列，所以你就从这个数开始，遍历直到找出一个满足没有被标记的数字，然后把它这个位置赋值，接着还要在分解你最新找到的这个数，并且把它的倍数标记，这样我们已经满足了大于等于字典序的要求了，接着可以接着在后面这些数，从2开始遍历，依次找到没有被标记的数，然后赋值，注意这儿你每次找到一个数，还是要标记它的倍数。

大概思路就是这样了

代码如下：

#include <bits/stdc++.h>using namespace std;int n,x;
const int Maxn = 2e6 + 100;
int prime[Maxn],vis[Maxn];void makee(int x) {for(int i = x; i <= Maxn; i += x)vis[i] = 1;return ;
}
void fenjie(int x) {int i = 2;while(i <= x) {if(x % i == 0) {if(!prime[i])makee(i);prime[i] = 1;x /= i;i = 2;} elsei++;}
}int main() {ios::sync_with_stdio(false);while(cin >> n) {int flag =  0;int  y;memset(vis,0,sizeof(vis));memset(prime,0,sizeof(prime));int id = 2,cnt = 0;for(int i = 0; i < n; i++) {cin >> x;if(flag) {cnt = i;for(int j = id; j <= Maxn; j++) {if(!vis[j]) {cout << j << " ";if(!prime[j])makee(j);id = j + 1;break;}}continue;}if(vis[x]) {for(int j = 2; j <= Maxn; j++)if(!vis[j]) {y = j;cout << y << " " ;flag = 1;break;}fenjie(y);vis[y] = 1;} else {cout << x << " ";fenjie(x);vis[x] = 1;}}cout <<endl;}}