有关勒让德定理的思考

前几天刷力扣遇到了一个考察阶乘性质的题

题目本身不难 可是要求O(logn)
很快想到可以将尾随0分解成2*5，如此一来题目就很清晰了
只需要找到有多少个2的倍数和5的倍数就行

---

根据次幂计数

很容易想到统计2^n^和5^n^各出现了多少次，对应加n，然后取两个和较小的那个
题中n<=10000，代码可以这么写

a=[5,25,125,625,3125]
b=[2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
suma=sumb=0
for i in range(n+1):
    for j in range(4):
        if i>=a[j] and i<a[j+1]:
            suma+=j+1
    if i>=a[4]:
        suma+=5
for i in range(n+1):
    for j in range(12):
        if i>=b[j] and i<b[j+1]:
            sumb+=j+1
    if i>=b[12]:
        sumb+=13
return min(suma,sumb)

---

这么写很直观，但是判断上太麻烦，能不能只要有i>a[j]就计数呢？

勒让德定理

这就该引出勒让德定理了：

直观来说就是将竖着的楼梯横着计数
于是乎代码就可以写成这样:

a=[5,25,125,625,3125]
b=[2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
for i in range(5):
    a[i]=n//a[i]
for i in range(13):
    b[i]=n//b[i]
return min(sum(a),sum(b))

---

进一步优化

看起来就简介多了，实际上这种形式已经能击败100%了
但是在思考阶乘中2和5出现的次数时不难发现，2的次数总少于5
于是干脆舍弃对2计数，可以再精简一些:

a=[5,25,125,625,3125]
for i in range(5):
    a[i]=n//a[i]
return sum(a)

如此这道题从算法层面就圆满了

tips

这道题最佳写法如下:

ans = 0
while n:
    n //= 5
    ans += n
return ans

对空间做了进一步优化