SRM661 Div1 Easy "MissingLCM"
解法
N + 1 ~ Mの中に、1 ~ Nの素因数を全て持っている必要がある。
例えばN = 10であれば、1 ~ 10に2^3, 3^2, 5^1, 7^1の素因数がある。
それぞれ11(N + 1)以上で、どの数であればその素因数を持つかを見ていくと、
2^3は2^3 * 2 = 16が持つ
3^2は3^2 * 2 = 18が持つ
5^1は5^1 * 3 = 15が持つ
7^1は7^2 * 2 = 14が持つ
となり、11 ~ 18で1 ~ 10の素因数を全て持つこととなる。
ソースコード
bool P[1000010]; class MissingLCM { public: int getMin(int N) { long long ans = 2; for (int i = 0; i <= N; i++) { P[i] = true; } P[0] = P[1] = false; for (int p = 2; p <= N; p++) { if (!P[p]) continue; for (int i = p + p; i <= N; i += p) { P[i] = false; } // 素数だ! // 1~Nはこの素数をどれだけ持つ? long long x = 1; while (x * p <= N) { x *= p; } // それはいくつ以上の数字で超える?(ただしNより大きいもので) long long y = x; while (y <= N) { y += x; } // これの最大値をとってく ans = max(ans, y); } return (int)ans; } };