ARC067 C - Factors of Factorial

問題

整数$N$が与えられたときの，$N!$の正の約数の個数を$10^9+7$で割った余りを求める．

考え方

$N!$の素因数を｛$ p_0,p_1,...,p_k$｝とする．また，各素因数の個数をそれぞれ，｛$i_0, i_1,...,i_k$｝とする．この時，$N!$は以下のように表される：
$N! = p_0^{i_0} \cdot p_1^{i_1} \cdot ... \cdot p_k^{i_k}$.

従って，$N!$の約数の個数は，
$(i_0+1) \cdot (i_1+1) \cdot ... \cdot (i_k+1)$
となる．

以上のことから，$N!$の各素因数の個数を求めればその約数の個数が求められるということが分かる．

実装

ここでは，各素因数の数を数えるために，
$（N!に含まれる素因数pの個数）= \Sigma_{k=1}^{ \infty } \left[ \frac{n}{p^k} \right ] = \left[ \frac{n}{p^1} \right ] + \left[ \frac{n}{p^2} \right ] + ...$
を利用する（この定理の詳細はこちら）．

import math
N = math.factorial(int(input()))

res = 1
p = 2  # チェックする因数

# p<=sqrt(N)を満たす因数を調査すれば十分
while p*p <= N:
    i = 1
    # p^k(k=1~)の倍数の個数を数えて足し合わせていく
    while(N % p == 0):
        i += 1
        N //= p

    # N!の約数の個数は i_0*i_1*...*i_k
    res *= i
    p += 1

if(N != 1):
    res *= 2
print(res % (10**9+7))