C++计算 n! 中末尾零的数量

* @详细说明
 * 给定一个整数作为输入。目标是找出该数的阶乘结果中末尾零的数量。
一个数 N 的阶乘是范围 [1, N] 内所有数的乘积。
 * 
 * 我们知道，只有当一个数是 10 的倍数或者有因数对 (2, 5) 时，才会产生末尾零。
在任何大于 5 的数的阶乘中，该数的质因数分解里 2 的数量比 5 的数量多很多。
用一个数除以 5 的幂可以得到其因数中 5 的个数。所以，5 的个数就代表了末尾零的数量。

#include <cassert>   /// 用于断言
#include <iostream>  /// 用于输入输出操作

 /**
  * @命名空间 bit_manipulation
  * @brief 位操作算法
  */
namespace bit_manipulation {
    /**
     * @命名空间 count_of_trailing_ciphers_in_factorial_n
     * @brief 用于实现 [计算 n! 中末尾零的数量](https://www.tutorialspoint.com/count-trailing-zeros-in-factorial-of-a-number-in-cplusplus) 的函数
     */
    namespace count_of_trailing_ciphers_in_factorial_n {
        /**
         * @brief 计算阶乘末尾零的数量的函数
         * @param n 要计算其阶乘末尾零数量的数
         * @return count，n! 中末尾零的数量
         */
        uint64_t numberOfCiphersInFactorialN(uint64_t n) {
            // count 用于存储 n! 中 5 的个数
            uint64_t count = 0;

            // 不断用 n 除以 5 的幂并更新 count
            for (uint64_t i = 5; n / i >= 1; i *= 5) {
                count += static_cast<uint64_t>(n) / i;
            }

            return count;
        }
    }  // 命名空间 count_of_trailing_ciphers_in_factorial_n
}  // 命名空间 bit_manipulation

/**
 * @brief 自测实现
 * @returns 无
 */
static void test() {
    // 第一个测试
    std::cout << "第一个测试 ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
        numberOfCiphersInFactorialN(395) == 97);
    std::cout << "通过" << std::endl;

    // 第二个测试
    std::cout << "第二个测试 ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
        numberOfCiphersInFactorialN(977) == 242);
    std::cout << "通过" << std::endl;

    // 第三个测试
    std::cout << "第三个测试 ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
        numberOfCiphersInFactorialN(871) == 215);
    std::cout << "通过" << std::endl;

    // 第四个测试
    std::cout << "第四个测试 ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
        numberOfCiphersInFactorialN(239) == 57);
    std::cout << "通过" << std::endl;

    // 第五个测试
    std::cout << "第五个测试 ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
        numberOfCiphersInFactorialN(0) == 0);
    std::cout << "通过" << std::endl;
}

/**
 * @brief 主函数
 * @returns 程序退出时返回 0
 */
int main() {
    test();  // 运行自测实现
    return 0;
}

代码解释

1. numberOfCiphersInFactorialN 函数：

   • 该函数接收一个无符号 64 位整数n作为参数。
   • 使用一个for循环，不断用n除以 5 的幂（从 5 开始，每次循环乘以 5），并将商累加到count中。
   • 最后返回count，即n!中末尾零的数量。

2. test 函数：

   • 该函数用于进行自测，包含 5 个测试用例。
   • 每个测试用例使用assert宏来验证numberOfCiphersInFactorialN函数的输出是否符合预期。
   • 如果测试通过，会输出相应的信息。

3. main 函数：

   • 调用test函数进行自测。
   • 最后返回 0 表示程序正常退出。