7932: Rightmost non-zero Digit in N!
题目描述
The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example
N N!
0 1
1 1
2 2
3 6
4 24
5 120
10 3628800
For this problem, you are to write a program that can compute the rightmost non-zero digit of the factorial for N in base B.
输入
In the first line there is an integer T (T <= 100), indicates the number of test cases.
In each case, there is a single line with integers N and B
(0<=N<=10^7, 2<=B<=10^4).
输出
For each case, the output format is “Case #c: ans”.
c is the case number start from 1.
ans is the answer of this problem. The ans is in base 10.
See the sample for more details.
样例输入 复制
2
13 3
11 11
样例输出 复制
Case #1: 2
Case #2: 10
提示
Case #1:
13*12*11*10*9*8*7*6*5*4*3*2*1=6227020800 base 10, which in base 3 is
121001222020102200000, so the right-most non-zero digit is 2.