c055 - 00568 - Just the Facts

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 N! (N 的階乘) 從右邊算來，第一個非零數字。輸入 N 的範圍是 0 到 10000。

解題思路

直接計算 N! 的值會導致溢出，因此需要使用一些技巧來避免溢出。 觀察到題目只需要最後一個非零數字，因此可以每次計算階乘時，都去除尾部的零。 此外，只需要儲存最後五位數字，因為題目要求輸出的是個位數。 使用動態規劃的方式，從 0! 和 1! 開始計算，每次計算 i! 時，將 i! = i * (i-1)!，然後去除尾部的零，並只保留最後五位數字。

複雜度分析

• 時間複雜度: O(N)
• 空間複雜度: O(N)

程式碼

#include <iostream>
#include <iomanip>
using namespace std;
int a[10001]={0,1};
int main(){
	int n;
	for(int i=2;i<10001;i++){
		a[i]=a[i-1]*i;
		while(a[i]%10==0){
			a[i]/=10;
		}
		a[i]%=100000;
	}
	while(cin >> n){
		cout << setw(5) << n << " -> " << a[n]%10 << "\n";
	} 
}