素因数分解ゲー！　今なら ABC D あたりに出てきそう

問題概要

正の整数 $N$ が与えられる。

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

制約

$2 \le N \le 10^{8}$

解法 (1)：素因数分解

まず $N$ を素因数分解しよう。

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

とする。さらに、 $1, 2, 3, \dots$ をそれぞれ素因数分解していく。 $1, 2, \dots$ の素因子を寄せ集めたときに、

$p_{1}$ が $e_{1}$ 個以上
$p_{2}$ が $e_{2}$ 個以上
...
$p_{K}$ が $e_{K}$ 個以上

という条件を満たす瞬間を捉えられればよい。

ただし注意点として、 $N$ が大きな素数であったとする。この場合は $1, 2, 3, \dots$ と素因数分解していっても、 $M = N$ まで到達しない限り、 $N$ が素因数として登場しない。このままでは $O(N\sqrt{N})$ の計算量 (整数 $n$ の素因数分解には $O(\sqrt{N})$ を要する) となって間に合わない。

そこで、次のようにする。

$N$ の素因数 $p$ (指数を $e$ とする) ごとに考える。

$p, 2p, 3p, \dots$ に対して「 $p$ で何回割れるか」を求めて総和をとっていく。その値がはじめて $e$ を超える瞬間の値を $m$ とする。

素因数 $p$ ごとの $m$ の最大値が答えである

指数 $e$ としてありうる値は高々 $O(\log N)$ 程度 (大きくても 30 くらい) である。よって、それぞれの素因数に対して $O(\log N)$ 回程度の試行で済む。めちゃくちゃ速い。

コード

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

// 素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(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 N;
    cin >> N;
    auto pf = prime_factorize(N);
    long long res = 0;
    for (auto pa : pf) {
        long long p = pa.first, e = pa.second;
        long long sum = 0;
        for (long long m = p; m <= N; m += p) {
            sum += how_many(m, p);
            if (sum >= e) {
                res = max(res, m);
                break;
            }
        }
    }
    cout << res << endl;
}

解法 (2)：かなり楽な方法

もう少し賢い方法でやってみよう！　結論から述べると、次の方法で解ける！！

$N$ を素因数分解したとき、素因数に $\sqrt{N}$ 以上のもの ( $p$ とする) があるならば、 $M = p$ が答え
そうでないならば、 $1!, 2!, 3!, \dots$ を $N$ で割ったあまりを求めていき、初めて 0 になったときの $M$ が答え

まず、 $N$ の素因子 $p$ が $\sqrt{N}$ 以上であるとしよう。このとき、 $p$ の指数 $e$ は $e = 1$ ということで確定する。よって、

$N = p \times p_{1}^{e_{1}} \dots p_{K-1}^{e^{K-1}}$

というふうに表せる。ここで $N' = p_{1}^{e_{1}} \dots p_{K-1}^{e^{K-1}}$ とく。このとき、 $p$ 以外の素因数 $p_{i}$ に対しては、少なくとも $M = N'$ の時点で、 $M!$ の $p_{i}$ に対する指数が $e_{i}$ 以上となる。なぜなら $N'$ 自身が $p_{i}$ で $e_{i}$ 回割り切れるからだ。

一方、 $p \ge \sqrt{N}$ より、 $N' = \frac{N}{p} \le \sqrt{N}$ が成立するので、答えは $M = p$ で確定する。

$\sqrt{N}$ より大きい素因数がない場合

この場合は、 $M$ は高々 $O(\sqrt{N} \log N)$ で抑えられる。なぜならどの素因数も $\sqrt{N}$ より小さく、その指数も $O(\log N)$ で抑えられるからだ。

よって、少なくとも $M = O(\sqrt{N} \log N)$ 程度で $M!$ は $N$ で割り切れることになる。この程度ならば愚直計算で間に合う。

コード

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

// 素因数分解 (指数は要らない、素数のみ)
vector<long long> prime_factorize(long long n) {
    vector<long long> res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        while (n % p == 0) { n /= p; }
        res.push_back(p);
    }
    if (n != 1) res.push_back(n);
    return res;
}

long long solve(long long N) {
    auto pf = prime_factorize(N);
    for (auto p: pf) if (p * p >= N) return p;
    long long amari = 1;
    for (long long M = 1; M <= N; ++M) {
        amari = (amari * M) % N;
        if (amari == 0) return M;
    }

    // no reach
    return -1;
}

int main() {
    long long N;
    cin >> N;
    cout << solve(N) << endl;
}

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

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

JOI 春合宿 2007 day1-2 Factorial (難易度 5)

問題概要

制約

解法 (1)：素因数分解

コード

解法 (2)：かなり楽な方法

$\sqrt{N}$ より大きい素因数がない場合

コード