题目描述
阶乘最右非零。采用大步小步法。这是最优解,代码也是最简洁的。
2021-05-16:时间复杂度必须是logN,如何求阶乘从右向左第一个不为零的数?
样例
package main
import "fmt"
func main() {
i:=0
fmt.Scanf("%d",&i)
fmt.Println(FactRightNotZero(i))
}
func FactRightNotZero(n int) int {
ans := 1
for n > 0 {
if n%5 == 0 {
ans <<= n & 3 //这是精髓
n /= 5
} else {
ans *= n % 10
n--
}
ans %= 10
}
return ans
}
https://mp.weixin.qq.com/s?__biz=MzUzMTc3NzQzNA==&mid=2247485190&idx=1&sn=67f9b953f028eb85db24de6c6a68b13a&chksm=fabc15f3cdcb9ce5ceea08b1c1bef855c4d7aba9b8f9561bda7db99a23eefb2c612764c24869&token=2047822268&lang=zh_CN#rd