阶乘末尾零优化

在计算 (b!) 的末尾有多少个连续的0时,可以通过模拟阶乘的乘法来计算整个大数阶乘,再统计结果中末尾的0的数量。然而,当 (b) 很大时,这种直接模拟阶乘的方法会导致运行时间和空间效率较低,容易超时。

实际上,计算一个数的阶乘末尾有多少个0并不需要真的计算出整个阶乘。阶乘末尾0的数量实际上取决于阶乘中因子5的数量(因为2的数量总是比5多)。因此,可以采用数学方法来计算。

优化方法

计算 (b!) 末尾0的数量的核心在于统计从1到(b)中,能够被5整除的数的个数,以及更高次方(如25, 125, …)的个数。具体的公式为:

Pasted image 20240925122937.png

一直计算到 Pasted image 20240925123033.png

优化后的代码

#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;
}

解释

  1. i 从5开始,每次乘以5,直到 ( i > b ) 为止。
  2. b / i 表示当前阶乘数范围内包含多少个可以被当前的5次方整除的数。
  3. 将每一步的结果累加即可得到 (b!) 中因子5的总数,这就是末尾0的数量。

这种方法的时间复杂度是 (O(\log b)),相比原算法效率极高,能轻松处理非常大的 (b) 值,从而避免超时问题。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇