ACM-ICPC 2016 国内予選 C: 竹の花

,

solution

エラトステネスの篩っぽい感じにやる貪欲。 答が取り得る値の最大値を$A$として、$O(A \log \log A)$。 なお$A$の値は問題文に書いてあって、$A = 7368791$である。

  • $a \ge m$でかつまだ使われていないような最小の$a$について、それは使わなければならない。
  • $a$を使ったとき、$ka$ for all $k \ge 1$についてこれを使われたことにできる。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
const int size = 7368791 + 1;
int main() {
    while (true) {
        int m, n; cin >> m >> n;
        if (m == 0 and n == 0) break;
        vector<bool> used(size);
        int j = m;
        repeat (i,n) {
            while (used[j]) ++ j;
            for (int k = j; k < used.size(); k += j) {
                used[k] = true;
            }
        }
        while (used[j]) ++ j;
        cout << j << endl;
    }
    return 0;
}