ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, C 解答

C: 竹の花

問題

m以上の整数をn個選ぶ事を考える。「m以上の数の内、選ばれたどの数の倍数でもない数」の最小値をその選び方のスコアとする。任意の選び方のスコアの最大値を出力せよ。

解法

mちょうどを選ばないとスコアは最低なので当然選ぶ。
次に選ぶべきはmの倍数でない最小値。
次は、前2数のどちらの倍数でもない最小値。
以下繰り返し。

これはエラトステネスのふるいと同様のアルゴリズムである(m == 2ならエラトステネスのふるいに等しい)。
つまり、

1. 適度に大きいbool配列を持ち、falseで初期化
2. 小さい値から順に配列をみて、false ならそのインデックスの倍数を全てtrueに変更

これは最初の配列の長さをNとすると計算量はO(N log N)。Nが現実的なサイズなら十分間に合いそうだが最大値はサンプルで与えられているのでよい。

コード

#include<cstdio>

const int MAX = 7500111;
int N, M;
int C[MAX];

int main() {
    for (int tt=1; scanf("%d%d", &M, &N), N|M; tt++) {
	int cur = M;

	for (int i=0; i<N; i++) {
	    while (C[cur] == tt) cur++;

	    for (int j=cur; j<MAX; j+=cur)
		C[j] = tt;
	}

	while (C[cur] == tt) cur++;
	printf("%d\n", cur);
    }

    return 0;
}