C++描述 AcWing 1381. 階乘

 

  大家好，我叫亓官劼（qí guān jié ）

N 的階乘（記作 N!）是指從 1 到 N（包括 1 和 N）的所有整數的乘積。

階乘運算的結果往往都非常的大。

現在，給定數字 N，請你求出 N! 的最右邊的非零數字是多少。

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

輸入格式

共一行，包含一個整數 N。

輸出格式

輸出一個整數，表示 N! 的最右邊的非零數字。

資料範圍

1≤N≤1000

輸入樣例：

7      

輸出樣例：

4      

解法一 - 直接模拟

#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a = 1;
    for(int i = 1; i <= n; i++){
        // 防止溢出 取模
        a = (a*i) % 10000;
        while(a%10 == 0)
            a /= 10;
    }
    cout << a % 10;
    return 0;
}      

解法二 - 階乘分解

#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a = 1,d2 = 0, d5 = 0;
    for(int i = 1; i <= n; i++){
        int x = i;
        while(x % 2 == 0){
            d2++;
            x /= 2;
        }
        while(x % 5 == 0){
            d5++;
            x /= 5;
        }
        a = (a*x) % 10;//隻保留個位即可 
    }
    //乘上之前未乘的因數2和5，當2和5同為因數時相乘為0，直接去掉
    for(int i = 0; i < d2 - d5; i++)
        a = (a * 2) % 10;
    cout << a;
    return 0;
}