NewOJ 题解 [1037-阶乘末尾0的个数一] (Python)

NewOJ 题解 [1037-阶乘末尾0的个数一] (Python)

题目链接

题目描述

求N的阶乘末尾存在多少个0。

输入格式

输入存在多组测试数据，对于每组测试数据输入一个整数N(0<=N<=10^9)

输出格式

对于每组测试数据，输出一行表示答案。

输入样例

12
20

输出样例

2
4

思路

通过观察可得，从0开始数字每增加5时，阶层末尾0的个数会增加1个，当增加的5的次数为5的倍数的时候会在此基础上再加1

个。

阶乘末尾0的个数有以下递推表达式

Z = x//5 + x// 5 2 5^2 52 + x// 5 3 5^3 53+…+x// 5 n 5^n 5n

代码实现

import sys

for line in sys.stdin:
    x = eval(line)
    z = 0
    i = 5
    while x//i != 0:
        z += x//i
        i *= 5
    print(z)

时间复杂度: O(log n)

空间复杂度: O(1)