AcWing 1381. 阶乘

题目

N 的阶乘（记作 N!）是指从 1 到 N（包括 1 和 N）的所有整数的乘积。

阶乘运算的结果往往都非常的大。

现在，给定数字 N，请你求出 N! 的最右边的非零数字是多少。

例如 5!=1×2×3×4×5=120，所以 5! 的最右边的非零数字是 2。

输入格式：

共一行，包含一个整数 N。

输出格式：

输出一个整数，表示 N! 的最右边的非零数字。

数据范围

1≤N≤1000

输入样例：

7

输出样例：

4

思路分析：

这道题通过计算器的直观展示，我们可以看到从5的阶乘开始末尾有0所以而0是由2*5%10得出，所以我们可以分解成若干个质数相乘，即 2 α × 5 β × x 2^{\alpha}\times 5^{\beta}\times x 2α×5β×x我们现在要找到有多少个2和多少个5，然后除以 10 × min ⁡ { α , β } 10\times \min \left\{ \alpha ,\beta \right\} 10×min{α,β} 最后再取10的模，通过公式(a * b) % c = ((a % c) * (b % c)) % c可以避免溢出，边除边模。

代码：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, d_2 = 0, d_5 = 0, res = 1;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x = i;
        while(x % 2 == 0){
            x /= 2;
            d_2++;
        }
        while(x % 5 == 0){
            x /= 5;
            d_5++;
        }
        res = res * x % 10;
    }
    int k = min(d_2, d_5);
    for(int i = 0; i < d_2 - k; i++) res = res * 2 % 10;
    for(int i = 0; i < d_5 - k; i++) res = res * 5 % 10;
    cout << res % 10 << endl;
    return 0;
}

AcWing题解
题目链接