ICPC国内予選2016 C問題 : 竹の花

問題. 竹の花

種をまいてから $k$ 年周期で花を咲かす竹のことを $k$ 年竹と呼ぶ．今， $n$ 個のすべての区画のそれぞれに $m$ 年以上の周期の竹の種を1つまくことを考える．この時， $m$ 年以降できるだけ長い期間どこかの区画で花が咲くような種の植え方を考え，そのような植え方で $m$ 年以降でどの区画でも花が咲かない初めての年を答えよ．

制約： $2 \le m \le 100$ ，　 $1 \le n \le 500,000$

＊答えの上限は 7368791 (ヒントとして与えられている)

解法. エラトステネスの篩 + 素数定理

エラトステネスの篩の考え方を基にしたアルゴリズムを考える．
$m$ 年から毎年花が咲いているかを確認する． $i$ 年目で花が咲いておらず区画が開いている場合は $i$ 年竹を植えることにする．このとき， $i$ 年竹を植えると $i$ の倍数の年は花が咲く．花が咲いておらず区画が開いていない初めての年が答えとなる．
ある年で花が咲くかどうかを表す配列を持ちながら上のシミュレーションを行うと答えを求めることができるが，考えることが2つある．1つめは配列のサイズであるが，7368791年が答えの上限というヒントがあるのでその通りにする．2つめは計算時間の解析であるが，エラトステネスの篩を参考にすると， $k \le 7368791$ のとき $O(k \log \log k)$ 時間となる．

計算時間： $O(k \log \log k)$ 　 $(k \le 7368791)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int Solve(const int m, int n) {
    constexpr int MAX_Y = 7368792;
    vector<bool> year(MAX_Y, false);

    int idx = m;
    while (n--) {
        while (year[idx]) ++idx;
        for (int i = 1; i * idx < MAX_Y; ++i)
            year[i * idx] = true;
    }

    while (year[idx]) ++idx;

    return idx;
}

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

    int m, n;

    while (cin >> m >> n, m)
        cout << Solve(m, n) << '\n';

    return 0;
}