Question

数字游戏

玲玲喜欢通过玩数字游戏的方式来加深别人对她的印象。她最喜欢的一个数字游戏是让人给出一个数N，然后她会立即说出N的阶乘最末尾有多少个连续的零。很显然，这会让别人会对她印象深刻，因为，一般来说N!是一个非常大的数。例如，N为100时，100!会比地球上所有原子的数目还要大，但玲玲可以很快说出100!末尾有连续24个0。但是，她的一些朋友通常不是以10为进制的。这时，玲玲却不知道该怎么修改她的技巧来适应这些朋友了。

问题：
给出一个进制b和一个数n，计算当采用b进制时，n!末尾有多少个连续的0。例如，当b=2和n=5时，由于5!=120=1111000(2)，结果应该为3.

输入：
第一行包含了总的计算次数。接下来的每一行给出了不同情况下的问题中的两个数b(2 ≤ b ≤ 1 000)和n(1 ≤ n ≤ 1 000 000)，这两个数都是10进制的。

输出：
输出结果中，对每一次计算都以"Scenario #i:"开始，其中的i是从1开始的第i次计算。然后打印一行，输出：当采用b进制时，n!末尾有多少个连续的0（以十进制形式）。对每一次计算都以一个空白行结束。

输入样例：
3
2 5
10 100
45 10000

对样例的正确输出：
Scenario #1:
3

Scenario #2:
24

Scenario #3:
2498

帮帮我！！！！！

Answer 1

这个问题是对n!后面有几个0的变种.
如果是问n!最后有几个0应该怎么算?肯定不是先算出n!是几,然后再数0的吧.
思路是看n!能被多少个10整除,例如5!=120只能被一个10整除,所以10进制末尾是有1个0的.
那么同理,如果问5!=120转化成2进制后末尾有多少个0,实际就是5!能被多少个2整除,能被3个2整除,所以末尾就是3个0.
n进制就是逢n进位, 计算n!转换成x进制后就是看n!有多少个x做因子.

追问

算n！时越界了

追答

不要去算n!
稍微大一点就越界的.
例如求12进制的n!末尾有几个0,先分解因数12=3*2*2, 就是说12的因数有3和2
然后设置两个2变量,记录从1到n中整除3和2的个数!例如出现24的时候,24=3*2*2*2, 那么对记录3的那个变量+1, 对2的那个变量+2(因为有3个因子),然后都统计出来.然后看记录3的那个变量假设是10, 2的那个变量记录的是25, 就是说n!中有一部分分解是3^10*2^25, 然后看这个数能整除多少个12就行了.明显的,这个数有10个3, 25个2, 10个3能整除12中3这个因子10次, 25个2能整除12中2这个引子12次, 所以总体上能整除12共10次,所以末尾应该是10个0