ABC227 Divisors of Binomical Cofficient

自力AC

全ての積をとるのは巨大過ぎて不可能です。

$_{N}C_{K}=\frac{(N-K+1)\cdot \cdots \cdot (N-1)\cdot N}{1\cdot 2\cdot \cdots \cdot K}$

であり、また、約数の個数は素因数分解して、

$p_1^{e_1},p_1^{e_2},\cdots$

となった時、

$(e_1+1)(e_2+1)\cdots$
として求められます。

以上から、1つの方法として、

・分母分子の個々の整数を素因数分解して、素因数の個数をカウントする

・分子の素因数の個数から分母の素因数の個数を引く

ことで、積を取ることなく、素因数分解可能な方法があります。

この方法は、

$\sqrt{N}$ 以下の素数の個数をPとして、少なくとも $O(KP)$ の計算量は必要で、 $10^6$ 以下の素数の個数を調べると、78,498個なので間に合いません。

そこで、無駄となっている素数の試し割りの部分を改善します。

具体的には、分母分子ともに連続した整数であることを利用して、エラトステネスの篩の要領で素数pで除算する整数(pを約数にもつ整数)を決定していきます。

分子は元のエラトステネスの篩のように、配列のインデックスと整数を一致させられないので、開始となるN-K+1を素数pで割った余りから、除算を開始する整数を決定します。

具体的には、

$A=\{N-K+1, N-K+2,...,N-1,N\}$

について、素数 $p$ で除算する開始点は、

$i \leftarrow [p - \{(N-K+1)\ mod\ p\}] mod\ p$

となり(0-indexed)、

$i \leftarrow i+p$

と更新して除算していきます。

具体例を示しておきます。

初期状態

分子の積の個々の整数を配列Aにした時の一例

A = {30 31 32 33 34 35 36 37 38 39 40 41 42}

p = 5の時、30 mod 5 = 0なので、(5-0) mod 5=0で、i = 0, 5 ,10について5で割ります

A = {6 31 32 33 34 7 36 37 38 39 8 41 42}

ここで分子は素因数5を3つことがわかります。

p = 7の時、30 mod 7 = 2なので、(7-2) mod 7=5で、i = 5, 12について7で割ります

A = {6 31 32 33 34 1 36 37 38 39 8 41 6}

ここで分子は素因数7を2つことがわかります。

以下、p = 2,3についても同様

気をつける点として、除算すると余りが変わるので、 $N-K+1$ の代わりに $A_0$ を $p$ で割った余りを使用することはできません(これでWAをたくさん出しました)。

例えば、30を7で割った余りは2ですが、5で割って6になった後7で割った余りは6に変化します。

計算量はエラトステネスの篩と類似の処理は $O(NlogN)$ となり、今回もそれが適用されます。除算の回数は各整数について、除算の度に $\frac{1}{p}$ となることから高々 $logN$ 回となるので、 $O(KlogK \cdot logN)$ くらいです。

追記

K=0のときは例外となるので、この時は1を出力するようにします。

また、個数が1になったものは約数の計算に含めないようにします。

geam1113’s diary