UVa 568 Just the Facts

题目描述

题目要求计算N!N!N!的最后一位非零数字（即去掉末尾所有零后的最后一位）。NNN的范围为0≤N≤100000 \le N \le 100000≤N≤10000。

输入格式

输入包含多个整数，每行一个，以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个NNN，输出一行，格式为：NNN（右对齐宽度555）、->、最后一位非零数字。

样例

输入

1 2 26 125 3125 9999

输出

1 -> 1 2 -> 2 26 -> 4 125 -> 8 3125 -> 2 9999 -> 8

题目分析

本题的核心是计算阶乘的最后一位非零数字，不能直接计算阶乘（会溢出）。可以使用模运算和去除因子101010的方法。

算法

• 维护当前乘积的最后若干位（去除末尾零后），例如保留101110^{11}1011以内的值。
• 每次乘以iii，然后不断除以101010直到末尾非零。
• 取模一个足够大的数（如101110^{11}1011）以防止溢出。

复杂度分析

N≤10000N \le 10000N≤10000，可以预计算所有结果，查询O(1)O(1)O(1)。

代码实现

// Just the Facts// UVa ID: 568// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constlonglongintMOD=100000000000;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);longlongintlast_number[10001]={1};for(inti=1;i<=10000;i++){longlonginttemp=i;while(temp%10==0)temp/=10;temp*=last_number[i-1];while(temp%10==0)temp/=10;if(temp>MOD)temp%=MOD;last_number[i]=temp;}intn;while(cin>>n)cout<<setw(5)<<right<<n<<" -> "<<(last_number[n]%10)<<'\n';return0;}