D. Mahmoud and Ehab and another array construction task | Codeforces Round #473 (Div. 2)

辞書順最小にしたいので先頭からbの値を決めていく。 とりあえず、aの要素を使える限り使っていく。 例えば、入力例2は

a={10, 3, 7}
b={10, 3, 7} 

b[i]をa[i]の要素として使えるかどうかを判定するには、あらかじめ十分大きな素数の集合を用意しておく。a[i]を素因数分解して、素数の集合にすべての素因数が含まれているならば可。その場合、その素数の集合から素因数分解で得られた素数を取り除く。

しかし、a[i] = b[i]とできない添字iがあるかもしれない。たとえば、

2 7 8
2 7 9
    *

のような場合である。この場合、a[i]より大きい整数を昇順に見ていく。素数でなくてもよいので注意。もし、残った素数の集合で素因数分解できるならば、その値は使える値として最小である。なお、a[i]<=10⁵より、最悪でも10⁵を超える最小の素数まで見ればb[i]を得られる。

このようにa[i]<b[i]となる添字iが存在した場合、残りのj>i, b[j]を構成する方法は簡単。残った素数のリストから小さい順に素数を並べていけばいい。

最後に必要な素数の集合の大きさだが、10⁵以下の素数は10⁴個未満であり、またn<=10⁵より、10⁵+10⁴個ほどの素数があればよい。これには1500000以下の素数を列挙すれば十分。

vector<int> sieve(int n) {
    vector<bool> f(n + 1);
    for (int i = 3; i <= n; i += 2) f[i] = 1;
    for (int i = 3; i <= sqrt(n); i += 2) if (f[i]) for (int j = i * 3; j <= n; j += i) f[j] = 0;
    vector<int> res;
    if (n >= 2)res.push_back(2);
    for (int i = 3; i <= n; i += 2) if (f[i]) res.push_back(i);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    auto primes = sieve(1500000);

    set<int> P(all(primes));
    int N;
    cin >> N;
    vi A(N);
    rep(i, N)cin >> A[i];

    vi ps(100);
    int gr = 0;
    rep(i, N) {
        if (gr) {
            auto it = P.begin();
            cout << *it;
            P.erase(it);
        } else {
            auto factorize = [&](int a) {
                int m = 0;
                for (int j = 2; j*j <= a; ++j) {
                    if (a%j == 0) {
                        ps[m++] = j;
                        while (a%j == 0)a /= j;
                        if (!P.count(j)) return -1;
                    }
                }
                if (a > 1) {
                    ps[m++] = a;
                    if (!P.count(a))return -1;
                }
                return m;
            };

            int m = factorize(A[i]);

            if (m != -1) {
                cout << A[i];
                rep(j, m) P.erase(ps[j]);
            } else {
                gr = 1;
                int x;
                for (x = A[i] + 1;; ++x) {
                    m = factorize(x);
                    if (m != -1)break;
                }
                cout << x;
                rep(j, m)P.erase(ps[j]);
            }
        }
        cout << (i != N - 1 ? ' ' : '\n');
    }
}