解题思路

这是一道数学题，主要思路如下：

  1. 问题分析：

    • 求n!末尾有多少个0
    • n的范围是[1, 1000]
    • 需要考虑大数问题

  2. 解决方案：

    • 末尾的0来自2×5的组合
    • 2的个数总是充足的
    • 只需要统计5的个数
    • 需要考虑25、125等贡献多个5的数

  3. 实现细节：

    • 统计n/5的个数
    • 再统计n/25的个数
    • 依此类推直到n/5^k < 1

代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 统计5的个数
    int count = 0;
    while(n) {
        count += n/5;
        n /= 5;
    }
    
    cout << count << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 统计5的个数
        int count = 0;
        while(n > 0) {
            count += n/5;
            n /= 5;
        }
        
        System.out.println(count);
    }
}

def count_trailing_zeros(n: int) -> int:
    # 统计5的个数
    count = 0
    while n:
        count += n//5
        n //= 5
    return count

def main():
    n = int(input())
    print(count_trailing_zeros(n))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：数学
  • 时间复杂度： - 每次除以5，最多循环次
  • 空间复杂度： - 只需要常数空间