素因数分解の良問！ABC052/ARC067 Factor of Factorial を解いてみた！

こんばんは、Ruteです。
久々に良問を解いた気がします。
今回はABC052/ARC067 C - Factors of Factorialについて、私がどのようにACしたのかを解説したいと思います！(コードはPython3です)

ABC052(ARC067) C問題

問題概要:

整数$N$が与えられます。$N!$の正の約数を$10^9+7$で割ったあまりを求めて下さい。
制約:
$1≦N≦10^3$

解法:

$10^3!$は、計算すると$2568$桁程度の整数になります。これを愚直に素因数分解していっても良いのですが、間違いなく実行時間超過(TLE)になりそうです。

ここで、$N! = 1×2×3×... N$であることに着目すると、1からNまでのそれぞれを素因数分解した結果を合わせたリストを作成すれば、$N!$の素因数のすべてをまとめたリストが作成できそうです。

素因数分解のアルゴリズムについてまとめてみます。

素因数分解のアルゴリズム

(素因数分解したい数を$n$とします)

素因数分解.py

import math
def factorization(n):
    i = 2
    factors = []
    while i <= math.floor(math.sqrt(n)):
        print(i,n)
        if n%i == 0:
            factors.append(i)
            n //= i
        else:
            i += 1
    if n > 1:
        factors.append(n)
    return factors

1.i=2とします。
2.素因数のリストとして、factorを空のリストで定義します。
2.iが$ \lfloor \sqrt{n} \rfloor$を下回るまで以下のループを行います。
・$n$がiで割り切れるならiは素因数だからiをfactorに挿入し、$n$をiで割った商とする。
・$n$がiで割り切れないなら、iを+1する。
ループが終了した後、n > 1 なら、nは素因数になるからfactorに挿入します。
これで、factorが、$n$の素因数を示したリストになりました。

ACしたコード

D.py

import math
# 素因数分解
def prime_factorization(n):
    i = 2
    factors = []
    while i <= math.floor(n**0.5):
        if n%i == 0:
            factors.append(i)
            n //= i
        else:
            i += 1
    if n>1:
        factors.append(n)
    return factors
N = int(input())
ls = []
# コーナーケース
if N == 1:
    print(1)
else:
    for i in range(1,N+1):
      #1~Nの、それぞれで素因数分解した結果を1つのリストにする。
        ls.extend(prime_factorization(i))
    ls.sort()
    ans = 1 # ansはN!の約数の個数
    now = 1 # nowは現在の連続数
    now_2 = 0 #now_2は現在参照対象の数
    for i in range(len(ls)):
        if i == 0:
            now_2 = ls[i]
        else:
            if ls[i] == now_2:
                now += 1
            else:
                ans *= (now+1)
                now = 1
                now_2 = ls[i]
    ans *= (now+1)
    print(ans%(10**9+7))

おおよそのアルゴリズムとしては、

1. $N$を入力
2. $N$が1ならば1を出力し(コーナーケース)、そうでなければ3に移る
3. $1$から$N$までの素因数をまとめたリストを1つのリストlsにする。
4. lsをソートする
5. lsの各要素について、以下のループを行う
   ・ls[i]が前のlsと同じなら、連続数を1増やす
   ・ls[i]が前のlsと異なるなら、ansに(連続数+1)を乗算する。連続数を1にする
6. ans%$(10^9+7)$を出力してAC !
   (かなり大雑把な説明ですみません.... )

昨日、素因数分解が話題になっていたのですが、今日のよるかつで出題されたのがこの問題で、素因数分解をするという発想に気づいて解くことが出来たので良かったです！

ここまでの記事を見て、解法が良かった！分かりやすかった！等と思った方は「LGTM」ボタンを押して頂けると嬉しいです！

以上、ABC052/ARC067 C - Factors of Factorialの解説でした！