题目描述： 给你两个正整数n（1 <= n <= 1000000)和m（2 <= m <= 100), 请你计算n!转换为m进制后末尾0的个数。 如： n = 10, m = 10, 则输出2.
示例： 输入： n = 10 m = 10 输出：2
分析:
相同数字不同进制下末尾0的个数不一样， 而10进制是我们最常见的一种进制，因此我们首先以10进制为例来进行分析。
10 = 2 * 5 = 1 * 10。 我们只需要记录 n! 的阶乘中含有 2 的个数 和 含有 5 的个数，然后取最小值即可。（含有 55个1，1个10。）
对于 10! 的而言，含有9个2，2个5，最后末尾0的个数为2。其中 数字4 含有 2个人，数字6 含有 1 个2，数字8含有3个2。
于是我们猜测，n进制下末尾0的个数，n的因数的个数有关，每一对因数中个数最少的因数其确定作用。
根据上面的猜测我们来猜测 20！在 16进制中末尾0的个数。
16 = 1 * 16 = 2 * 8 = 4 * 4
20！里面 含有：
210 个 1
1 个 16
18个2
2个8
6个4
不同组的最少因数个数都不一样，所以我们很难进行确定。实际上 20! = 0x21c3677c82b40000, 末尾有4个0。这和上面所有因数的个数都不一样。
这是为什么？ 经过观察，以2 * 8 为例，有一些包含2 的元素，也有可能会包含8，或者3个包含1个2的元素，也可以合成 1 个8。所以我最先猜测因数可能有问题。
那么什么 因数一定不会由其他因数构成呢？ 换句话理解， 什么因数除了它本身以外没有其他因数？ 答案： 质因数。
当我明确了这一点后我重新进行分析。 16 需要4 个2，而20！ 里面包含了18个2， 所以 18 // 4 = 4。刚好等于末尾0的个数。
基于这个猜想，我尝试了8进制。 18 // 3 = 6. 20! = ‘0o207033167620255000000’。 刚好 6 个0。
这里是质因数唯一的情况，如果要求 24进制的呢？ 质因数里面有 3 个 2， 1个3。如何操作？
以24进制中 40! 为例，先找出24的质因数情况。 有 3 个 2， 1个3。
然后再求 40! 中包含的 2 和 3 的个数。 其中包含 38 个 2 ，15个3。 末尾0的个数 ans = min( 38//3, 15 // 1)
那么我们如何确定 40! 中包含了多少个 2 呢？ 其实很简单。
40 // 2 = 20; 20 // 2 = 10; 10 // 2 = 5; 5 // 2 = 2; 2 // 2 = 1; 1 / / 2= 0
总个数 = 20 + 10 + 5 + 2 + 1 + 0 = 38。品一品，细品。
所以 n! 在 m 进制下末尾0的个数算法步骤就是。
- 确定 m 进制 质因数数组 a_lst，以及对应因数的个数的数组 b_lst， 一共有 k 种质因数。
- 确定 n! 中 质因数数组a_lst 对应因数的个数的数组 c_lst。
取 数组 { c_lst[i] // b_lst[i] 1 <= i <= k } 种的最小值。
代码里面使用了 字典来做 一一对应的关系。需要好好品一品。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 专门用来找对应质因数的个数
def get_num(num, m):
res = 0
while num:
res += num//m
num //= m
return res
ans_dict = {}
tm = m
# 确定质因数
i = 2
while tm != 1:
while tm % i == 0:
temp = ans_dict.get(i, 0)
ans_dict[i] = temp + 1
tm //= i
i += 1
res_dict = {}
# 求上面的 n! 的 c_lst
for key, value in ans_dict.items():
res_dict[key] = get_num(n, key)
ans = 999999999999999999999
# 取上面 c_lst[i] // b_lst[i] 的最小值
for key, value in res_dict.items():
ans = min(ans, value//ans_dict[key])
print(ans)