AtCoder Beginner Contest 227 G 問題 Divisors of Binomial Coefficient

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

二項係数 $\dbinom{N}{K}$ の正の約数の個数を求めよ.

制約

$1 \leq N \leq 10^{12}$
$1 \leq K \leq \min (10^6,N)$

解法

約数に関する問題なので, 素因数分解に着目する.

$\dbinom{N}{K}=\dfrac{N(N-1) \cdots (N-K+1)}{K (K-1) \cdots 2 \cdot 1}$

である. ここで, $\mathbb{P}$ で正の素数全体の集合として,

$\displaystyle N(N-1) \cdots (N-K+1)=\prod_{p \in \mathbb{P}} p^{a_p},\quad K(K-1) \cdots 2 \cdot 1=\prod_{p \in \mathbb{P}} p^{b_p}$

で表せるとき, 各素数 $p \in \mathbb{P}$ に対して, $e_p:=a_p-b_p$ とすると, 任意の素数 $p$ に対して, $e_p \geq 0$ であり,

$\displaystyle \dbinom{N}{K}=\prod_{p \in \mathbb{P}} p^{e_p}$

である. よって, $a_p, b_p$ を求めることを目標にする.

さて, 2つの正の整数 $X,Y$ について,

$\displaystyle X=\prod_{p \in \mathbb{P}} p^{x_p}, \quad Y=\prod_{p \in \mathbb{P}} p^{y_p} \Rightarrow XY=\prod_{p \in \mathbb{P}} p^{x_p+y_p}$

であるから, 結局は $1,2, \dots, K-1,K$ と, $N-K+1, \cdots, N-1,N$ の高々 $2K$ 個の整数に関する素因数分解が求められればよい.

ここで, $N \leq 10^{12}, K \leq 10^6$ なので, 試し割り方やポラード・ロー素因数分解法では無理がある. しかし, $N-K+1, \cdots, N-1,N$ が連続した $K$ 個の整数であるから, 以下のような方法を取ることができる.

$a_p, b_p$ を求める.

$\sqrt{N}$ 以下の素数を全て求める. これはエラトステネスの篩で計算できる. そして, $\sqrt{N}$ 以下の素数で素因数分解したい $K$ 個の整数を割り切り, $a_p$ を計算する. $\sqrt{N}$ 以下の素数を全て見た場合, 残った整数は $1$ 以外の可能性があるが,