競技プログラミング

ARC067A Factors of Factorial

問題

https://atcoder.jp/contests/arc067/tasks/arc067_a
素因数分解の問題です。試し割り法と呼ばれるアルゴリズムで解くことができます。

アルゴリズムの詳細はこちらをご覧ください。
NTL1A Prime Factorize

方針

約数の個数は、　各素因数で何度割ることができるかがわかれば計算することができます。この問題はNの上限が小さいため、愚直に素因数分解のループを回せば十分です。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MOD = 10**9+7
def factorize(N):
    n = N
    fact = []
    for i in range(2,int(N**0.5)+1): # intに変換すること
        while(n%i==0):
            n //= i #  整数除算(//)を使うこと
            fact.append(i)
    if n!=1:
        fact.append(n)
    return fact
N = int(input())
cnt = [0] * (N+1)
for n in range(1,N+1):
    fact = factorize(n)
    for f in fact:
        cnt[f] += 1

ans = 1
for n in range(N+1):
    ans *= (cnt[n]+1)
    ans %= MOD
print (ans)

関連記事

他にも競技プログラミングの記事を書いています。

記事情報

  • 投稿日：2020年5月6日
  • 最終更新日：2020年5月6日