WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};