[BOJ 6662] Divisors

문제 링크 : https://www.acmicpc.net/problem/6662

문제

Your task in this problem is to determine the number of divisors of $n \choose k$. Just for fun -- or do you need any special reason for such a useful computation?

입력

The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.

출력

For each instance, output a line containing exactly one integer -- the number of distinct divisors of $n \choose k$. For the input instances, this number does not exceed 2⁶³ - 1.

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

이항 계수 $\binom{n}{k}$의 약수 개수를 구하는 문제다. 약수의 개수는 소인수 분해를 통해 지수들에 $1$을 더해 곱한 값이다.

1. $431$까지의 모든 자연수에 대해 소인수의 개수를 $DP$ 테이블에 미리 계산한다
2. $\binom{n}{k} = n! / (k!(n-k)!)$ 성질을 이용하여 각 소인수의 최종 지수를 계산한다

\[\text{Exponent}(p) = \text{Count}(n!, p) - \text{Count}(k!, p) - \text{Count}((n-k)!, p)\]

1. 각 소인수의 지수($e$)에 대해 $(e+1)$을 모두 곱하여 약수의 개수를 도출한다

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍