素因数分解を上手に活用しよう！

問題へのリンク

問題概要

正の整数 $N$ が与えられる。 $N!$ の正の約数の個数を 1000000007 で割った余りを求めよ。

制約

$1 \le N \le 10^{3}$

考えたこと

「約数の個数」をまともに考察する場合には、素因数分解が役にたつことが多い。一般に正の整数 $N$ が

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

と素因数分解できるとき、 $N$ の正の約数の個数は

$(e_{1} + 1)(e_{2} + 1)\dots(e_{K}+1)$

と表せるのだ。

よって、この問題は「 $N!$ の素因数分解を求める」問題へと帰着された。

$N!$ の素因数分解

まず、 $N \le 1000$ より、 $N!$ の素因数分解に登場する素数は 1000 以下であることがわかる。そこで、1000 以下の素数を列挙して、各素数 $p$ について、「 $N!$ の素因数分解における $p$ の指数」を求めることにしよう。

それはつまり、「 $N!$ が $p$ で何回割り切れるか」を求められれば良い。これは数学 IA の教科書にも載っている有名問題だ。次のように求められる。

$\lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^{2}} \rfloor + \lfloor \frac{N}{p^{3}} \rfloor + \dots$

これを求める計算量は $O(\log N)$ となる。

よって、全体の計算量は、 $N$ 以下の素数の個数を $P$ として、 $O(P \log N)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

vector<int> Era(int n) {
    vector<bool> isprime(n, true);
    vector<int> res;
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n; ++i) isprime[i] = true;
    for (int i = 2; i < n; ++i) {
        if (isprime[i]) {
            res.push_back(i);
            for (int j = i*2; j < n; j += i) isprime[j] = false;
        }
    }
    return res;
}

int main() {
    long long N, res = 1;
    cin >> N;
    
    // N 以下の素数
    vector<int> primes = Era(N + 1);
    for (auto p : primes) {
        // 各素数 p について、N! を何回割り切るかを求める
        long long exp = 0, N2 = N;
        while (N2) {
            exp += N2 / p;
            N2 /= p;
        }
        
        // res に (exp + 1) をかける
        res = res * (exp + 1) % MOD;
    }
    cout << res << endl;
}

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

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

AtCoder ABC 052 C - Factors of Factorial (3Q, 緑色, 300 点)

問題概要

制約

考えたこと

$N!$ の素因数分解

コード