165AC - ABC052C: Factors of Factorial

ABC052-C (300 points)
問題

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

  •  1 \leq N \leq 10^3
方針


 N = \prod_i p_i^{a_i}

 \ \ \ \ であるとき, 約数の個数  d(N)


 d(N) = \prod_i (a_i + 1)

  • modの計算は掛け算の途中でしても良いので, 各素因数についてmodを取りながら約数を数えていく.
参考

sucrose.hatenablog.com
qiita.com

import math

# input
N = int(input())

def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = dict()

    while prime_factor_table[n] != 0:
        if prime_factor_table[n] in prime_count.keys():
            prime_count[prime_factor_table[n]] += 1
        else:
            prime_count[prime_factor_table[n]] = 1
        n = int(n/prime_factor_table[n])
    if n in prime_count.keys():
        prime_count[n] += 1
    else:
        prime_count[n] = 1
    return prime_count

Ps = dict()
P_1000 = prime_factor_table(1000)
ans = 1

for i in range(2, N + 1):
    P_i = prime_factor(i, P_1000)
    for k in P_i.keys():
        if k in Ps.keys():
            Ps[k] += P_i[k]
        else:
            Ps[k] = P_i[k]

for k in Ps.keys():
    ans = (ans * (Ps[k] + 1)) % (10 ** 9 + 7)

print(ans)