AtCoder ABC052 C - Factors of Factorial

題意

• N!の約数の数を述べよ(mod 10^9 +7)
• 制約: 1 <= N <= 1000

考え方

例えば、$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 $の場合、因数は30個となる。
これらを因数分解して考えると、$ 6 = 3 \times 2 $ であり、、$ 4 = 2 \times 2 $であるから、
$6! = 3 \times 2 \times 5 \times 2 \times 2 \times 3 \times 2 $と言い換えられる。
この右辺の任意の組み合わせが約数となるが、上記の式から適当に数と取ってしまうと、2を2つとる場合が複数あり、4という約数を複数カウントしてしまう。ここで、上記の素因数を以下のように整理する。

5
3 3
2 2 2 2

となる。かきかたを変えると、

5を: とらない, 1つとる
3を: とらない, 1つとる, 2つとる
2を: とらない, 1つとる, 2つとる, 3つとる, 4つとる

のように、各素因数について見つかった数+1が考えられるのでこれをかければ、この数の独立した約数の数をカウントできることに他ならない。

Nがたかだか1000のため、素因数分解は愚直でよく、また、カウントする配列も愚直に実装すればよい。ある約数について、発見された数が0である場合は、選ばないという選択肢しかないので、1として組み合わせの数に掛け算すればよい。

コード

因数分解モジュール: https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8

mod = 1000000000 + 7
 
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr
 
n = int(input())
dat = [0] * 2000 # 約数として求められたある数の合計
 
# N! の各要素の素因数分解をする
res = 1
for i in range(1, n + 1):
    d = factorization(i)
    for j in range(len(d)):
        dat[d[j][0]] += d[j][1]
 
for i in range(2, n + 1):
    res *= (dat[i] + 1)
    res %= mod
 
print(res)