Task

Find the number of positive divisors of \(\binom{N}{K}\).

Constraints

• \(1 \le N \le 10^{12}\)
• \(0 \le K \le \min(10^6, N)\)

Editorial

For brevity, denote \(N (N - 1) \dots (N - K + 1)\) as \(\ffact{N}{K}\).¹

The problem boils down to factorizing \(K!\) and \(\ffact{N}{K}\).

Factorize \(K!\)

Some quick observations:

• Prime factors of \(K!\) are not greater than \(K\).
• 素数 \(p\) 在 \(K!\) 里的次数可表为 \(\floor{K / p} + \floor{K / p^2} + \dots\)。
• For any positive integers \(a, b, c\), \(\floor{a \over bc} = \floor{\floor{a\over b} \over c}\).

Therefore, factorizing \(K!\) can be implemented as

std::vector<int> get_primes(int n); // returns primes not greater than n
auto primes = get_primes(K);
std::vector<int> e(K + 1);
for (int p : primes) {
  int t = K;
  while (t >= p) {
    e[p] += t /= p;
  }
}  

Factorize \(\ffact{N}{K}\)

\(\ffact{N}{K}\) can be factorized via the sieve of Eratosthenes。

把 \(N \dots (N - K + 1)\) 的素因子分成两类：大于 \(\sqrt{N}\) 的和不大于 \(\sqrt{N}\) 的。一个不大于 \(N\) 的正整数至多有一个大于 \(\sqrt{N}\) 的素因子。