G - Divisors of Binomial Coefficient Editorial by en_translator
If the prime factorization of a positive integer \(M\) is \(M=\prod_i p_i^{e_i}\), then \(M\) has \(\prod_i (e_i+1)\) number of positive divisors. Therefore, if we can factorize \(\binom{N}{K}\) into primes, then we can find the answer.
Since \( \displaystyle \binom{N}{K}=\frac{N(N-1)\dots(N-K+1)}{1\cdot 2 \cdot \cdots \cdot K}\), if we can factorize \(2K\) integers, \(1,2,\ldots,K\) in the numerator and \(N-K+1,\ldots,N-1,N\) and denominator, then we can find the result of prime factorization of \( \binom{N}{K}\) too. Now let us consider how to find this.
The prime factorization can be done by the following steps, analogous to the Eratosthenes’ sieve:
Pseudocode
primes=[2,3,5,...] // Primes less than K
A=[0,1,2,...,K] // A[i] = i
divisors=[[],[],...,[]]
for p in primes
for i=p to K step p
while A[i]%p==0
divisors[i].append(p)
A[i]/=p
The time complexity of this algorithm is \(O(K\log\log K)\), same to that of Eratosthenes’ sieve.
Analysis
First, we consider the complexity of the 5th through the 8th line. Since the number of $i$ such that the while statement is executed $n$ or more times is at most $\left\lfloor \frac{K}{p^n}\right\rfloor $, so the upper bound of the complexity is $\sum_{n=1}^{\infty} \frac{K}{p^n}=\frac{K}{p-1}$. Therefore, when $p$ loops over all primes less than $K$, then the overall time complexity is $ \sum_{p\leq K, p:\text{prime}} \frac{K}{p-1}=O(K\log\log K)$.
The prime factorizations of \(N-K+1,\ldots,N-1,N\) can be done in almost identical way. Similar to prime factorization by trial division, we use the property that after dividing by all primes less than or equal to \(\sqrt{N}\), the remaining value is a prime.
Pseudocode
for p in primes // Primes less than or equal to sqrt(N)
for i in {Multiple of p between N-K+1 and N, inclusive}
while A[i]%p==0
divisors[i].append(p)
A[i]/=p
for i=N-K+1 to N
if A[i]!=1
divisors[i].append(A[i])
The time complexity of this algorithm is \(O(M\log\log M)\), including the time required to enumerate the primes, where \(M=\max(\sqrt{N},K)\).
It is easy to find the answer for the original problem from these results.
Note that we can reorder the process so that we do not need to store the result of the prime factorization.
posted:
last update: