题目描述题目要求计算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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constlonglongintMOD100000000000;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);longlongintlast_number[10001]{1};for(inti1;i10000;i){longlonginttempi;while(temp%100)temp/10;temp*last_number[i-1];while(temp%100)temp/10;if(tempMOD)temp%MOD;last_number[i]temp;}intn;while(cinn)coutsetw(5)rightn - (last_number[n]%10)\n;return0;}