P2277 - Rightmost non-zero Digit in N!

内存限制：128 MB 时间限制：2.000 S

评测方式：文本比较命题人：

提交：6 解决：1

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.

2277: Rightmost non-zero Digit in N!