アルゴリズムとデータ構造

素因数分解を使った約数の個数

正の整数 n の約数の個数を求めるために、単純に 1 から n までの数をすべて走査し、n を割り切れるものをカウントする方法があります。

しかし、このやり方は非常に遅くなってしまいます。実は、約数の個数は、n の素因数を見つけることで効率よく求められます（素因数の探索は O(n)\mathcal{O}(\sqrt{n}) 程度の計算量で済みます）。

具体的には、ある整数をその素因数の積として表したとき、

2=214=227=7124=23⋅3175=31⋅5284=22⋅31⋅71300=22⋅31⋅52n=p1e1⋅p2e2⋅p3e3⋅...⋅pkek\begin{aligned} 2 &= 2^1 \\ 4 &= 2^2 \\ 7 &= 7^1 \\ 24 &= 2^3 \cdot 3^1 \\ 75 &= 3^1 \cdot 5^2 \\ 84 &= 2^2 \cdot 3^1 \cdot 7^1 \\ 300 &= 2^2 \cdot 3^1 \cdot 5^2\\ n &= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot ... \cdot p_k^{e_k} \\ \end{aligned}

各素因数の指数に 1 を加え、それらをすべて掛け合わせると、n の約数の個数が求まります。

2=21  ⟹  1+1=24=22  ⟹  2+1=37=71  ⟹  1+1=224=23⋅31  ⟹  (3+1)⋅(1+1)=875=31⋅52  ⟹  (1+1)⋅(2+1)=684=22⋅31⋅71  ⟹  (2+1)⋅(1+1)⋅(1+1)=12300=22⋅31⋅52  ⟹  (2+1)⋅(1+1)⋅(2+1)=18n=p1e1⋅p2e2⋅p3e3⋅...⋅pkek  ⟹  (e1+1)⋅(e2+1)⋅(e3+1)\begin{aligned} 2 &= 2^1 &&\implies 1 + 1 &&= 2\\ 4 &= 2^2 &&\implies 2 + 1 &&= 3\\ 7 &= 7^1 &&\implies 1 + 1 &&= 2\\ 24 &= 2^3 \cdot 3^1 &&\implies (3 + 1) \cdot (1 + 1) &&= 8\\ 75 &= 3^1 \cdot 5^2 &&\implies (1 + 1) \cdot (2 + 1) &&= 6\\ 84 &= 2^2 \cdot 3^1 \cdot 7^1 &&\implies (2 + 1) \cdot (1 + 1) \cdot (1 + 1) &&= 12\\ 300 &= 2^2 \cdot 3^1 \cdot 5^2 &&\implies (2 + 1) \cdot (1 + 1) \cdot (2 + 1) &&= 18\\ n &= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot ... \cdot p_k^{e_k} &&\implies (e_1 + 1) \cdot (e_2 + 1) \cdot (e_3 + 1) \\ \end{aligned}

この方法を実装するときは、n の素因数を見つける手順とほぼ同じ要領で行えます。以下のコードは、その一例です（コード自体ではなく、コメント部分のみ翻訳対象です）:

n = ...
p, divisors = 1, 1          # 素因数と、約数の個数

while p * p <= n:           # p <= sqrt(n) の間くり返す
    p += 1                  # 各反復で p に 1 を加える
    if n % p != 0:          # n が p で割り切れなければ何もしない
        continue
    
    exp = 0                 # 指数をカウントする変数
    while n % p == 0:       # 割り切れる限り p で割る
        n //= p
        exp += 1
    divisors *= exp + 1     # (指数 + 1) を積にかける

if n > 1:                   # p が sqrt(n) を超える場合、n は素因数として残っている
    divisors *= 2           # 指数が1の素因数を追加
print(divisors)

チャレンジ: n の約数の個数を求める

整数 n が与えられたとき、n の約数の個数を求めてください。

入力

最初の行に整数 n が 1 つ与えられます (2 ≤ n ≤ 10910^9)。

出力

n の約数の個数を出力してください。

例

Input

入力

8

4

17

2

2048

12

48

10

ボーナス: なぜ素因数の指数に 1 を加え、すべて掛け合わせると約数の個数になるのか？

n の約数を「素因数の組み合わせ」として考えると納得しやすいです。各素因数が何回使われるかは指数で表されますが、0 回使う場合も含める必要があるため、指数に 1 を足して組み合わせの数を数えています。その結果、生じる積が約数の総数を表すことになります。n 自身や 1 もこの方法でしっかりカウントされますし、最終的にはすべての素因数の可能な組み合わせを網羅するため、これが n の約数の個数を正しく示す理由です。

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB