MegaFactorialDiv2
SRM 569 · 2012-12-13 · by gojira_tc
SRM 569 · 2012-12-13 · by gojira_tc · Dynamic Programming, Simple Math
Problem Statement
Problem Statement
The factorial of the k-th order of a number n is denoted n!k and defined by the following recurrences:
1) n!k = n!(k-1) * (n-1)!k for n > 0 and k > 0
2) n!k = 1 for n = 0
3) n!k = n for k = 0
For example, 7!1 = 7! (the traditional factorial), and 5!3 = 5!2 * 4!3 = (5!1 * 4!2) * 4!3.
You are givenint s N and K. Compute the number of distinct divisors of the number N!K. Return the computed number modulo 1,000,000,009.
1) n!k = n!(k-1) * (n-1)!k for n > 0 and k > 0
2) n!k = 1 for n = 0
3) n!k = n for k = 0
For example, 7!1 = 7! (the traditional factorial), and 5!3 = 5!2 * 4!3 = (5!1 * 4!2) * 4!3.
You are given
Constraints
- N will be between 1 and 1000, inclusive.
- K will be between 1 and 100, inclusive.
Examples
0)
3 1 Returns: 4
3!1 = 3! = 6. The divisors of 6 are 1, 2, 3 and 6.
1)
3 2 Returns: 6
3!2 = 3!1 * 2!2 = 3! * 2!1 * 1!2 = 3! * 2! * 1!1 * 0!2 = 3! * 2! * 1! * 1 = 12. The divisors of 12 are 1, 2, 3, 4, 6 and 12.
2)
4 2 Returns: 18
4!2 is equal to 288.
3)
6 3 Returns: 1392
4)
100 2 Returns: 321266186
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MegaFactorialDiv2 with a public method int countDivisors(int N, int K) · 51 test cases · 2 s / 256 MB per case