色々な考え方ができる楽しい問題ですね！　3 通りの解法を自分なりに咀嚼して整理しました。

問題へのリンク

問題概要

2 以上の整数 $K$ が与えられる。

$N!$ が $K$ の倍数となるような最小の整数 $N$ を求めよ。

制約

$2 \le K \le 10^{12}$

考えること：まずは素因数分解

この問題のように、「倍数」とか「約数」といった問題を考えるときには、素因数分解することが有効であることが多い。与えられる整数 $K$ を素因数分解してみよう。 $K$ を素因数分解した式は、

$K = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \dots \times p_{m}^{e_{m}}$

というふうに表すことが多い。 $p_{1}, \dots, p_{m}$ が素因数で、 $e_{1}, \dots, e_{m}$ が指数。

たとえば、 $K = 600$ であれば

$K = 2^{3} \times 3 \times 5^{2}$

と素因数分解できるので、

$m = 3$
$p_{1} = 2, e_{1} = 3$
$p_{2} = 3, e_{2} = 1$
$p_{3} = 5, e_{3} = 2$

ということになる。

一般の整数に関する問題を、素数べきに関する問題へ帰着できる！

$K$ を素因数分解することのメリットは、一般の整数に関する問題を、素数べきに関する問題へ帰着できることだ！！

$N!$ が $K = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \dots \times p_{m}^{e_{m}}$ の倍数であるということは、次の条件がすべて成り立つことと同値なのだ。

$N!$ が $p_{1}^{e_{1}}$ の倍数である
$N!$ が $p_{2}^{e_{2}}$ の倍数である
$\dots$
$N!$ が $p_{m}^{e_{m}}$ の倍数である

つまり、一般に $p$ を素数、 $e$ を正の整数として

$N!$ が $p^{e}$ で割り切れる条件

を考察する問題を考えればよいということになるのだ！！

このように、一般の整数に関する問題を、素数べき $p^{e}$ に関する問題へと帰着する論法は頻出！！！

ここまで考えたうえで、この問題にはさまざまな解法が考えられる！！

解法 (1)：愚直に試していく (= 公式解説)

私たちは、 $N!$ が $p^{e}$ で割り切れるような、最小の整数 $N$ を求めたい。

まず、 $N$ が $p$ の倍数の場合だけ考えれば十分なことに注意しよう。

このことの感覚的理解を試みる。たとえば $p = 3$ であるとしよう。 $1!, 2!, 3!, 4!, \dots$ を素因数分解したときの $3$ の指数を順に求めると次のようになる。

$1! = 1$
$2! = 2$
$3! = 3^{1} \times 2$ (更新！)
$4! = 3^{1} \times 8$
$5! = 3^{1} \times 40$
$6! = 3^{2} \times 80$ (更新！)
$7! = 3^{2} \times 560$
$8! = 3^{2} \times 4480$
$9! = 3^{4} \times 4480$ (更新！)
$10! = 3^{4} \times 44800$
$\dots$

これを見てわかることは、 $1!, 2!, 3!, 4!, \dots$ を素因数分解したときの $3$ の指数は、 $n!$ の $n$ が $3$ の倍数である地点でしか更新が発生しないことだ。このことはもちろん一般の素数 $p$ に対して成り立つ。

以上より、 $N!$ が $p^{e}$ の倍数となるような最小の $N$ は次のようにして求められる。

$n = p, 2p, 3p, \dots$ に対して、 $n!$ を素因数分解したときの $p$ の指数を順に求めていき、その値が $e$ 以上となる最小の $n$ が答えである

この解法は実はとても高速だ。

なぜなら、最悪でも $n = ep$ は確実に条件を満たすのだ。つまり、 $n = p, 2p, 3p, \dots$ と探索するのを高々 $e$ 回繰り返せば答えが求められる。

ここまでの解法をまとめると、次のようになる。

$K = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \dots \times p_{m}^{e_{m}}$ と素因数分解する
各 $i = 1, 2, \dots, m$ に対して、 $n!$ が $p_{i}^{e_{i}}$ の倍数となる最小の $n$ を求め、それを $n_{i}$ とおく ( $e_{i}$ 回以下の探索で求められる)
$n_{1}, n_{2}, \dots, n_{m}$ の最大値が答えである

計算量は、最初の素因数分解がボトルネックで $O(\sqrt{K})$ となる。

コード

AC コードを開く

#include <bits/stdc++.h>
using namespace std;

// 素因数分解
using pll = pair<long long, long long>;  // (素因数, 指数)
vector<pll> prime_factorize(long long n) {
    vector<pll> res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        long long e = 0;
        while (n % p == 0) { n /= p, ++e; }
        res.emplace_back(p, e);
    }
    if (n != 1) res.emplace_back(n, 1);
    return res;
}

// n が p で何回割れるかを求める
long long how_many(long long n, long long p) {
    long long res = 0;
    while (n % p == 0) {
        n /= p;
        ++res;
    }
    return res;
}

int main() {
    // 入力
    long long K;
    cin >> K;

    // K を素因数分解する
    vector<pll> pf = prime_factorize(K);

    // 各素因数ごとに求めていく
    long long res = 0;
    for (auto [p, e] : pf) {
        long long f = 0;  // n! を素因数分解したときの p の指数
        for (long long n = p; ; ++n) {
            f += how_many(n, p);
            if (f >= e) {
                res = max(res, n);
                break;
            }
        }
    }
    cout << res << endl;
}

解法 (2)：二分探索 (= ユーザー解説 by miscalculation53)

解法 (1) と同様に、 $N!$ が $p^{e}$ で割り切れるような、最小の整数 $N$ を求めたい。

素朴な方法としては、二分探索法も考えられる。二分探索法にするにあたっては、次の判定問題が解ければよい。

整数 $n$ が与えられる。

$n!$ が $p^{e}$ で割り切れるかどうかを判定してください。

これを求めるためには、「 $n!$ が $p$ で何回割れるか」が求められればよい。これは受験でもおなじみの典型問題だ！！

たとえば、 $n = 10, p = 2$ としよう。 $10!$ が $2$ で何回割れるかは下図のように求められる。

$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ の「 $2$ で割れる回数」はそれぞれ $0, 1, 0, 2, 0, 1, 0, 3, 0, 1$ 回になる。この合計値が答えである。つまり、下図の「赤い正方形」の個数が答えになる。しかしその個数は、 $0, 1, 0, 2, 0, 1, 0, 3, 0, 1$ を足すのではなく、横に足すと計算しやすい。つまり、

10 ÷ 2 = 5
10 ÷ 4 = 2 ... 2
10 ÷ 8 = 1 ... 2

というようにして、5 + 2 + 1 = 8 回と計算すると楽なのだ。

具体的には、次のようなコードで計算できる。なお、この方法をルジャンドルの定理という。仰々しい名前だが、車輪の再発明も十分に可能な話だと思う！

int num = 0;
while (n) {
    num += n / p;
    n /= p:
}

ここまでの解法をまとめると、次のようになる。

$K = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \dots \times p_{m}^{e_{m}}$ と素因数分解しておく
で二分探索する。その際に、がで割り切れるかどうかを判定する問題を次のように解く
- 各 $i = 1, 2, \dots, m$ に対して、 $n!$ が $p_{i}$ で割れる回数が $e_{i}$ 以上であるかどうかを判定する

計算量は、解法 (1) と同じく、素因数分解がボトルネックで $O(\sqrt{K})$ となる。

コード

AC コードを開く

#include <bits/stdc++.h>
using namespace std;

// 素因数分解
using pll = pair<long long, long long>;  // (素因数, 指数)
vector<pll> prime_factorize(long long n) {
    vector<pll> res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        long long e = 0;
        while (n % p == 0) { n /= p, ++e; }
        res.emplace_back(p, e);
    }
    if (n != 1) res.emplace_back(n, 1);
    return res;
}

// n! が p で何回われるかを求める
long long Legendre(long long n, long long p) {
    long long res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}

int main() {
    // 入力
    long long K;
    cin >> K;

    // K を素因数分解する
    vector<pll> pf = prime_factorize(K);

    // 二分探索する
    long long low = 0, high = K;  // K! は確実に K で割り切れる
    while (high - low > 1) {
        long long n = (low + high) / 2;

        // n! が各 p で割れるかを判定
        bool ok = true;
        for (auto [p, e] : pf) {
            if (Legendre(n, p) < e) ok = false;
        }

        // 二分探索の更新
        if (ok) high = n;
        else low = n;
    }
    cout << high << endl;
}

解法 (3)：√N より大きい素因数がないときは愚直でよい！(= ユーザー解説 by cn449)

最後は天才的な解法！！

まず、 $K$ の最大の素因数を $p$ とする。たとえば

$K = 24$ のとき、 $p = 2$
$K = 40$ のとき、 $p = 5$
$K = 101$ のとき、 $p = 101$
$K = 143$ のとき、 $p = 13$

という具合だ。このとき、実は、次の天才的な場合分けで解けてしまうのだ。

$p \gt \sqrt{K}$ のとき： $N = p$ が答え！！
そうでないとき： $N = 1, 2, 3, \dots$ に対して、順に $n!$ を $K$ で割っていき、はじめて割り切れるような $N$ が答え

1. について

1 については、 $K$ を素因数分解したときに、 $p$ の指数が 1 であることに着目する。さらに、ちゃんと解析すると次のように証明できる。

1. の証明を開く

まず、 $K$ の素因子 $p$ が $\sqrt{K}$ より大きいとしよう。このとき、 $p$ の指数 $e$ は $e = 1$ ということで確定する。よって、 $K$ を素因数分解すると、

$K = pL$ ( $L$ を素因数分解すると素因数に $p$ は含まない)

という形になる。

まず、 $N!$ が $K$ で割り切れるためには、 $N \ge p$ が必要であることを示す。 $p$ は素数なので、 $N \lt p$ の場合は $N!$ が $p$ では割り切れない。そして、 $p$ で割り切れない整数は $K$ で割り切れることはない。よって、 $N \lt p$ のとき、 $N!$ は $K$ では割り切れない。

次に、 $p!$ が $K$ で割り切れることを示す。 $p$ と $L$ が互いに素であることから、 $p!$ が $p, L$ で割り切れることを示せばよい。 $p!$ が $p$ で割り切れることは自明なので、 $p!$ が $L$ で割り切れることを示す。

$p \gt \sqrt{K}$ より、 $L = \frac{K}{p} \lt \sqrt{K}$ が成り立つ。よって、 $p! = L! \times (L + 1) \times (L+2) \times \dots \times p$ は確かに $L$ で割り切れる。よって、 $p!$ は $K$ で割り切れることが示された。

以上より、 $N!$ が $K$ の倍数となる最小の $N$ は $N = p$ となる。

2. について

2 についての解法は、一見すると計算量が危ないが、1 の場合を除外したことで実は計算量的に現実的であることが示せるのだ。

具体的には、条件を満たす最小の $N$ が、高々 $O(\sqrt{K} \log K)$ で抑えられることが言える。どの素因数も $\sqrt{K}$ より小さく、その指数も $O(\log K)$ で抑えられるからだ。

コード

愚直解法の方は、実装の工夫が必要だ。次のように書きたいところだが、 $K$ が $10^{12}$ と大きいため、amari * n の部分でオーバーフローが発生する可能性がある。

long long amari = 1;
for (long long n = 1; n <= K; ++n) {
    amari = (amari * n) % K
    if (amari == 0) {
        cout << n << endl;
        return 0;
    }
}

そこで、 $n!$ を $K$ で割っていくのではなく、次のように考えることにする。

$\frac{1!}{K}$ を約分して既約分数にする
$\frac{2!}{K}$ を約分して既約分数にする
$\frac{3!}{K}$ を約分して既約分数にする
$\dots$

というように計算していき、はじめて分母が $1$ になった箇所が答えになる。

コード

AC コードを開く

#include <bits/stdc++.h>
using namespace std;

// 素因数分解 (素因数が小さい順)
using pll = pair<long long, long long>;  // (素因数, 指数)
vector<pll> prime_factorize(long long n) {
    vector<pll> res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        long long e = 0;
        while (n % p == 0) { n /= p, ++e; }
        res.emplace_back(p, e);
    }
    if (n != 1) res.emplace_back(n, 1);
    sort(res.begin(), res.end());
    return res;
}

int main() {
    // 入力
    long long K;
    cin >> K;

    // K を素因数分解する
    vector<pll> pf = prime_factorize(K);
    long long p = pf.back().first;  // K の最大の素因数

    // K が √K より大きい素因数をもつとき
    if (p > K / p) {
        cout << p << endl;
        return 0;
    }
    
    // そうでない場合は愚直に解く
    // n! / K を約分したときの分母を求めていく
    long long bunbo = K;
    for (long long n = 1; n <= K; ++n) {
        long long div = gcd(n, bunbo);  // 何で約分するか
        bunbo /= div;  // 約分したあとの分母を求める
        if (bunbo == 1) {
            cout << n << endl;
            return 0;
        }
    }
}

なお、別解 by cn449 では、さらに突っ込んだ考察をして、実装を大幅に楽にしている！！

「2 の場合」の $n$ の探索範囲が実際には $2000000$ 以下で十分であることを明らかにしている。さらに、わざわざ素因数分解する必要もない実装になっている！！

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 280 D - Factorial and Multiple (緑色, 400 点)

問題概要

制約

考えること：まずは素因数分解

一般の整数に関する問題を、素数べきに関する問題へ帰着できる！

解法 (1)：愚直に試していく (= 公式解説)

コード

解法 (2)：二分探索 (= ユーザー解説 by miscalculation53)

コード

解法 (3)：√N より大きい素因数がないときは愚直でよい！(= ユーザー解説 by cn449)

1. について

2. について

コード

コード