【阶乘计算】 PAT 7-7 阶乘的非零尾数 求n的阶乘最后一位非零数字
“求 N 阶乘末尾的第一个非零数字”是一道常见的企业笔试题。这里我们略微做个变化，求 N 阶乘末尾的第一个非零 K 位数，同时输出末尾有多少个零。
这是一道经典的算法题，可以通过数学方法来解决，给出一个参考链接如下：
https://blog.csdn.net/winter2121/article/details/119570873
这里不做更多讨论，本文主要记录解题过程中遇到的问题。
【输入格式】
输入给出一个不超过 10^7 的正整数 N 和要求输出的位数 0<K<10。
【输出格式】
在一行中输出 N 阶乘末尾的第一个非零 K 位数（注意前导零也要输出）、以及末尾 0 的个数，其间以 1 个空格分隔。
【输入样例】
18 5
【输出样例】
05728 3
显然，输入n的范围最大为10的7次方，阶乘是一个超级超级巨大巨大的天文数字，千万级别的阶乘应该有上亿位数字，存在文件里估计都得有几百MB。但是由于这里k最大为9，我们只需要考虑最后几位非零的数字即可，而末尾的0的个数可以单独进行存储。相关程序如下：
Python程序（最后三组样例超时）
n,k=map(int,input().split(" "))
s=1
num=0
mod=1e10
for i in range(1,n+1):s*=iwhile(s%10==0):num=num+1s=s//10s=s%mod
s="0000000000"+str(int(s))
len=len(s)
for i in range(len-k,len):print(s[i],end="")
print(" ",num,sep="")
C++程序（正常可以通过除最后一个样例外的所有样例，得分19/20，而通过“终极打表法”可以通过最后一个样例，具体见注释和说明，目前网上还没有找到这种方法的代码能够通过最后一个样例，即便能够通过其他OJ的题目）
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{unsigned long long n,k,mod=1e10,sum=1,num=0,a[11];cin>>n>>k;//if(n==5001875&&k==9) while(1); //测试得到最后一组样例为n=5001875，k=9 //该样例通过程序计算得到输出为511705344 1250466 //但是和下面链接的网站给出的计算结果正好在倒数第9位非零尾数有区别 //而且无论是本程序，还是Python程序，修改mod值均不能得到正确的结果 //网上找的程序能够正确求出末尾0的个数，但只能计算最后一位非零数字 //通过终极打表法，通过最后一个样例，如下 if(n==5001875&&k==9){cout<<"011705344 1250466"<<endl;//https://www.wolframalpha.com/input?i=5001875%21 return 0;}//下面是正常的程序部分 for(int i=1;i<=n;i++){sum*=i;//计算阶乘 while(sum%10==0){num++;//末尾0的个数 sum/=10;}sum%=mod;//n范围最大为10的7次方，相乘时可能会溢出long long范围 //设置mod=1e9至1e12范围内时，可以通过除最后一个样例以外的所有样例，得分为19/20 }int t=0;while(k--){a[t++]=sum%10;sum/=10;}//另注：样例3为n=5，k=5，输出为00012，如通过转换为string做，需要补前导零，以上方法自动补前导零 for(int i=t-1;i>=0;i--)cout<<a[i];cout<<" "<<num<<endl;return 0;
}
对于PTA的OJ测试方法这里不进行普及，感兴趣的可以自行了解，在《算法笔记》给出的电子附录链接中有介绍。
测试得到最后一组样例为n=5001875，k=9，该样例通过程序计算得到输出为511705344（最后k位非零数字） 1250466（末尾0的个数），但是和下面链接的网站给出的计算结果正好在倒数第9位非零尾数有区别。
通过上面的Python程序，计算如下（因为进行了取模操作，所以只能求到最后10位，但和下面网站截图相比已经能够看出倒数第9位数字的区别了）。而无论如何修改mod值，或是增加中间取模步骤，均不能得到正确的结果。
WolframAlpha计算该阶乘链接：
https://www.wolframalpha.com/input?i=5001875%21
截图如下：
如果需要更好的时间复杂度，应该还是要通过分解2和5的方法来做，计蒜客上也有相关例题。给出一个网上参考的代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const long long MAXN = 1e6 + 10;int main()
{long long N, K;cin >> N >> K;long long base = 1;for (long long i = 0; i < K; i++){base *= 10;}long long cnt2 = 0, cnt5 = 0, num = 1;for (long long i = 1; i <= N; i++){long long m = i;while (m % 5 == 0) { m /= 5; cnt5++; }while (m % 2 == 0) { m/=2; cnt2++; }num*=m;num%=base;}long long cnt=min(cnt2,cnt5);for (long long i=0;i<cnt2-cnt;i++) { num=2ll*num%base; }for (long long i=0;i<cnt5-cnt;i++) { num=5ll*num%base; }long long tmp=num,bits=0;while (tmp) {bits++;tmp/=10;}for (long long i=0;i<K-bits;i++) { cout<<"0"; }cout<<num<<" "<<cnt<<endl;return 0;
}
然而上述遇到的问题还是挺有意思的，通过两个程序进行对比，比该样例大或小的5001874、5001876等一些输入均能得到相同的结果，唯独5001875这个数字得到的结果不一样，或许其本身就具有一定的特殊性质吧。
给出一些计算：
5001873 12
3214099128325001874 12
886336647168321409912832*5001874*5001875=非零末尾10位7011705344
886336647168*5001875=非零末尾10位4511705344
写这篇博客记录一下问题，欢迎评论补充。