TopCoder SRM 569 - 1000: MegaFactorial

Problem Statement

题目简述

我们作出如下递归定义：

f[n][k] = f[n][k-1] * f[n-1][k] (n>0,k>0)
f[n][k] = 1 (n=0)
f[n][k] = n (k=0)

给出N,K,B，求f[N][K]在B进制下末尾0的个数，答案对10^9+9取模。
1 <= N <= 10^9,1 <= K <= 16,2 <= B <= 10

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 given ints N, K and B. Count the number of trailing zeros in the number N!K when it is written in base B and return it modulo 1,000,000,009.

Definition

Class MegaFactorial
Method countTrailingZeros
Parameters int , int , int
Returns int
Method signature int countTrailingZeros(int N, int K, int B)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Constraints

N will be between 1 and 1,000,000,000 (10^9), inclusive.
K will be between 1 and 16, inclusive.
B will be between 2 and 10, inclusive.

Test cases

input
- N 6
- K 1
- B 4
output
Returns 2

note

6!1 = 6! = 23100 in base 4.
input
- N 4
- K 2
- B 6
output
Returns 2

note

4!2 = 4!1 * 3!2 = ... = 4! * 3! * 2! = 1200 in base 6.
input
- N 10
- K 3
- B 10
output
Returns 22
input
- N 50
- K 10
- B 8
output
Returns 806813906
input
- N 1000000000
- K 16
- B 2
output
Returns 633700413

back to the menu

SRM 569 1 1000 MegaFactorial

Problem Statement

Definition

Limits

Constraints

Test cases