D. Mahmoud and Ehab and another array construction task

题目链接

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

题解

中档题。题意大概是对于给定序列,求出某一字典序最小的序列满足

  • 每一个元素不小于2
  • 字典序不小于原序列
  • 对于任意两个元素最大公约数为1
  • 长度与原序列相同

从头开始读入每一个元素,分为以下几种情况讨论

  • 当前位置之前的每一个元素均与原序列相同,则当前位置找到满足条件的不大于原序列当前位置的最小的值,并且筛去它的所有因数的倍数。
  • 当前位置之前存在与原序列不同的元素,当前位置为允许的最小元素并且将它的所有倍数标记(不需要考虑因数,因为当前元素一定是质数)

除此之外有很多细节方面的优化请参考代码。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1 << 30;
const ll INF = 1ll << 60;

int pri[MAXN];
bool isFilled[MAXN];
bool isoccued[MAXN];
int input[MAXN];

int n;
int q1, q2, q3, now, num;
bool apped;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    for (int i = 2; i < MAXN; i++) {
        if (!isFilled[i]) pri[num++] = i;
        for (int j = 0; j < num && i * pri[j] < MAXN; j++) {
            isFilled[i* pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }

    cin >> n;
    now = 2;
    for (int _ = 1; _ <= n; _++) {
        cin >> input[_];
        q1 = input[_];
        q2 = 0;
        if (isoccued[q1]) {
            if (apped) {
                for (int i = now; i < MAXN; i++) {
                    if (!isoccued[i]) {
                        cout << i << ' ';
                        for (q3 = i; q3 < MAXN; q3 += i)
                            isoccued[q3] = true;
                        now = i + 1;
                        break;
                    }
                }
            }
            else {
                for (int i = q1; i < MAXN; i++) {
                    if (!isoccued[i]) {
                        cout << i << ' ';
                        while (i >= pri[q2]) {
                            while (i%pri[q2] == 0) {
                                if (isoccued[pri[q2]] == false) {
                                    for (q3 = pri[q2]; q3 < MAXN; q3 += pri[q2])
                                        isoccued[q3] = true;
                                }
                                isoccued[pri[q2]] = true;
                                i /= pri[q2];
                            }
                            q2++;
                        }
                        apped = true;
                        break;
                    }
                }
            }
        }
        else {
            if (!apped) {
                cout << q1 << ' ';
                while (pri[q2] <= q1) {
                    while (q1%pri[q2] == 0) {
                        if (isoccued[pri[q2]] == false) {
                            for (q3 = pri[q2]; q3 < MAXN; q3 += pri[q2])
                                isoccued[q3] = true;
                        }
                        isoccued[pri[q2]] = true;
                        q1 /= pri[q2];
                    }
                    q2++;
                }
            }
            else {
                for (int i = now; i < MAXN; i++) {
                    if (!isoccued[i]) {
                        cout << i << ' ';
                        for (q3 = i; q3 < MAXN; q3 += i)
                            isoccued[q3] = true;
                        now = i + 1;
                        break;
                    }
                }
            }
        }
    }
}

标签: math, constructive algorithms, greedy, number theory

添加新评论