下記問題で約数の個数を求める必要があり、調べたところ公式があったのでメモを残します。

約数の個数の求め方

公式はシンプルです。下記サイトに詳細が載っています。

かんたんに処理の流れを確認してみます。

素因数分解をする
各素因子が何回でてくるか(何乗になっているか)を調べる
例として、30 を素因数分解すると、"30 = 2¹ * 3¹ * 5¹"となる。これを公式に当てはめると (1+1) * (1+1) * (1+1) = 8 となる。30の約数は"1,2,3,5,6,10,15,30"であることから正しいと言える。

ARC067での使い方

今回の問題では、与えられた整数Nの階乗の約数の個数を求める必要がある。

たとえば、N = 6の時、 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720の約数の個数を求めることとなる。この場合、各値(1-6)の素因子とその個数をもとめ、足し合わせることで階乗の値における各素因子が出てくる総和を求めることが可能です。例を示します。

4! = 4 * 3 * 2 * 1

4 = 2²

2 = 2¹

なので、 4! = 2² * 2¹ * 3 * 1 となる。指数の公式から4! = 2²⁺¹ * 3 * 1 とすることができる。つまり、階乗において各値の素因数の指数同士を足し合わせればNの階乗した値の各素因子の数が求められます。そしたらあとは公式に当てはめるだけです。

問題の実装を載せます github.com