165AC - ABC052C: Factors of Factorial
ABC052-C (300 points)
問題
整数 が与えられるとき, の正の約数の個数を で割った余りを求める.
方針
であるとき, 約数の個数 は
- 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)