阶乘末尾零优化
这个程序的主要目的是计算 (b!) 的末尾有多少个连续的0。当前的算法通过模拟阶乘的乘法来计算整个大数阶乘,再统计结果中末尾的0的数量。然而,当 (b) 很大时,这种直接模拟阶乘的方法会导致运行时间和空间效率较低,容易超时。
实际上,计算一个数的阶乘末尾有多少个0并不需要真的计算出整个阶乘。阶乘末尾0的数量实际上取决于阶乘中因子5的数量(因为2的数量总是比5多)。因此,可以采用数学方法来计算。
优化方法
计算 (b!) 末尾0的数量的核心在于统计从1到(b)中,能够被5整除的数的个数,以及更高次方(如25, 125, …)的贡献。具体的公式为:
一直计算到
优化后的代码
#include<iostream>
using namespace std;
int main()
{
int b;
cin >> b;
int count = 0;
for (int i = 5; i <= b; i *= 5)
{
count += b / i;
}
cout << count << "\n";
return 0;
}
解释
i
从5开始,每次乘以5,直到 ( i > b ) 为止。b / i
表示当前阶乘数范围内包含多少个可以被当前的5次方整除的数。- 将每一步的结果累加即可得到 (b!) 中因子5的总数,这就是末尾0的数量。
这种方法的时间复杂度是 (O(\log b)),相比原算法效率极高,能轻松处理非常大的 (b) 值,从而避免超时问题。
当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »