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

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

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

素因数分解ゲー! 今なら 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;
}