USACO 3.2.1 Factorials

最新推荐文章于 2022-12-02 22:06:55 发布

devillaw_zhc

最新推荐文章于 2022-12-02 22:06:55 发布

阅读量382

点赞数

分类专栏： USACO 文章标签： c++

本文链接：https://blog.csdn.net/devillaw_zhc/article/details/7756467

版权

USACO 专栏收录该内容

15 篇文章

订阅专栏

本文介绍了一种计算特定数值阶乘结果尾数的方法。通过两次遍历：首先统计因数5的数量；然后移除所有成对的2和5，接着进行逐位相乘并取模10得到最终尾数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

先扫一遍统计因数 5 的个数 k （因数 2 的个数显然大于因数 5 的个数）

再扫一遍把 k 个 5 和 k 个 2 除掉，那么接下来每次结果都mod 10就是了

/*
PROG:fact4
LANG:C++
*/

#include <cstdio>

using namespace std;

int n, ans = 1, cnt2, cnt5;

int main()
{
    freopen("fact4.in", "r", stdin);
    freopen("fact4.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1;i <= n;++i)
    {
        int j = i;
        while (j % 5 == 0)
        {
            ++cnt5;
            j /= 5;
        }
    }
    cnt2 = cnt5;
    for (int i = 1;i <= n;++i)
    {
        int j = i;
        while (j % 5 == 0 && cnt5) --cnt5, j /= 5;
        while (j % 2 == 0 && cnt2) --cnt2, j /= 2;
        ans = (ans * j) % 10;
    }
    printf("%d\n", ans);
}