階乘問題分為幾類：
1.求階乘末尾0的個數，，直接除以5，累加即可。
2.求階乘的結果一共有多少位，stirling公式：n！≈sqrt(2*PI*n) * (n/e)^n，直接取以10為底的對數，整數部分即為位數。 3.求階乘的最後非零位，這類問題比較復雜，專題中我們著重討論這個問題
首先看POJ1150
題目大意：求n的m排列的最後非零位。
題目分析：n的m排列即P(n,m)=n!/(n-m)!，所以這題是求兩個階乘商的最後非零位。我們處理階乘時一般是逐個處理。首先看普遍性的對於一個數n的階乘，我們如何處理它的末尾非零位。
10的因子是2和5，這兩個數不屬於模10的縮系，所以我們在處理數時要剔除掉這兩個因子，剔除所有數中含5和2這兩個因子。
首先我們用f(n,x)表示小於等於n的數中，末尾位x的數的個數。n我們可以分解為1,3,5,7,9... 2,4,6,8,10...
因為我們將偶數中的2因子剔除了，所以2,4,6,8,10...實際上又變成了1,3,5,7,9...
所以我們可以得到遞推式f(n,x)=f(n/2,x)+g(n,x)，g(n,x)表示的是小於等於n的奇數中尾數為x的數的個數。
那麼g(n,x)怎麼求呢，首先n/10必定是其中一部分，其次要看n>=x是否成立，成立就加1，不成立就不加。最後一點要注意，我們在奇數中還有汗5因子的數，所以要剔除掉5這個因子，比如5 15 25 35 45... 剔除了5之後又變成了1 3 5 7 9...，所以g(n,x)=n/10+(n%10>=x)+g(n/5,x)。
有了這兩個遞推式再加上求5因子和2因子個數的遞歸除法，我們很快就能得到2因子個數，5因子個數，末尾位3 7 9因子的個數。下面我們要列個循環表mod2[4]={6,2,4,8},mod3[4]={1,3,9,7},mod7[4]={1,7,9,3},mod9[4]={1,9,1,9}，表示的是各個因子自己相乘時尾數的循環節，這裡要特別注意一點，由於2非模10的縮系，所以2^0=1，這一點要格外注意，所以只有它循環節不是從0開始，0要單獨處理。因為n-m的階乘必定是n的階乘的子集，所以我們可以直接用因子數相減即可。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5);
cnt[3]=get(n,3)-get(n-m,3);
cnt[7]=get(n,7)-get(n-m,7);
cnt[9]=get(n,9)-get(n-m,9);
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
printf("%d\n",res%10);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5);
cnt[3]=get(n,3)-get(n-m,3);
cnt[7]=get(n,7)-get(n-m,7);
cnt[9]=get(n,9)-get(n-m,9);
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
printf("%d\n",res%10);
}
return 0;
}
再來看POJ3406
求n!/(m!*(n-m)!)的最後非零位
與上題一樣，但是由於m的階乘和n-m的階乘的乘積並不是n的階乘的子集，但是我們可以通過觀察發現，只有n的階乘中3的個數會少於m的階乘和n-m的階乘3的數目之和，但是我們不要擔心，這個時候我們可以通過將n的階乘中的9的個數分解得到。還有一種方法是再多加一個循環模（我表示不理解）
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2)-getpow(m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5)-getpow(m,5);
cnt[3]=get(n,3)-get(n-m,3)-get(m,3);
cnt[7]=get(n,7)-get(n-m,7)-get(m,7);
cnt[9]=get(n,9)-get(n-m,9)-get(m,9);
cnt[3]+=cnt[9]*2;cnt[9]=0;
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
printf("%d\n",res%10);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2)-getpow(m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5)-getpow(m,5);
cnt[3]=get(n,3)-get(n-m,3)-get(m,3);
cnt[7]=get(n,7)-get(n-m,7)-get(m,7);
cnt[9]=get(n,9)-get(n-m,9)-get(m,9);
cnt[3]+=cnt[9]*2;cnt[9]=0;
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
printf("%d\n",res%10);
}
return 0;
}
最後看一個BT題ZOJ1222
這題在很多OJ上都有，只不過數量級很小，可以用上面的方法輕松ac，但是這題據說輸入是一個字符串，可能有100+位，所以面對如此高精度大數，要用新的方法來解決。
思路不變，還是以2和5為核心，把每個數最後的尾數乘起來，只是由於數的極速擴大，我們不能用原來的遞歸求解了，要用到一個循環節：int mod[10]={1,1,2,6,4,4,4,8,4,6};這個表示從0乘到9（將5換為1）的非0尾數。當n<5時，直接輸出mod[n].我們要去掉尾數0，就要去掉相同數量的2和5，我們發現2的個數是遠遠多於5的個數，並且因子2的數目是最多的，所以最後得到的結果一定是一個偶數，於是存在這樣一個特殊的尾數除法：2/2=6,4/2=2,6/2=8,8/2=4。同時在除以2的個數時，還是由於2的個數比較多的原因，是存在一個除法的循環節的，循環節的長度為4.並且這10個尾數相乘為6，當n>10時，我們可以得到一個公式：
此時我們就可以應用這個公式進行求解了，值得注意的是n是一個非常大的數，在除以5的時候我們可以利用高精度除法。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str[1001];
int mod[10]={1,1,2,6,4,4,4,8,4,6};
int a[1001];
int getAns(int cnt)
{
if(cnt==1&&a[0]<5)return mod[a[0]];
int res=0;
int w=a[0];
for(int i=cnt-1;i>=0;--i)
{
res=res*10+a[i];
a[i]=res/5;
res=res%5;
}
if(a[cnt-1]==0)--cnt;
int m=(a[1]*10+a[0])%4;
int tmp=getAns(cnt)*mod[w]*6%10;
while(m--)
{
if(tmp==2)tmp=6;
else if(tmp==6)tmp=8;
else tmp/=2;
}
return tmp;
}
int main()
{
while(~scanf("%s",str))
{
int len=strlen(str);
memset(a,0,sizeof(a));
for(int i=0;i<len;++i)
{
a[i]=str[len-1-i]-'0';
}
int ans=getAns(len);
printf("%d\n",ans);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str[1001];
int mod[10]={1,1,2,6,4,4,4,8,4,6};
int a[1001];
int getAns(int cnt)
{
if(cnt==1&&a[0]<5)return mod[a[0]];
int res=0;
int w=a[0];
for(int i=cnt-1;i>=0;--i)
{
res=res*10+a[i];
a[i]=res/5;
res=res%5;
}
if(a[cnt-1]==0)--cnt;
int m=(a[1]*10+a[0])%4;
int tmp=getAns(cnt)*mod[w]*6%10;
while(m--)
{
if(tmp==2)tmp=6;
else if(tmp==6)tmp=8;
else tmp/=2;
}
return tmp;
}
int main()
{
while(~scanf("%s",str))
{
int len=strlen(str);
memset(a,0,sizeof(a));
for(int i=0;i<len;++i)
{
a[i]=str[len-1-i]-'0';
}
int ans=getAns(len);
printf("%d\n",ans);
}
return 0;
}
4.數字n是否可以表示為若干個不同的階乘的和
實際上這個問題跟數論無關，是一道搜索的問題
的第2358題，由於n比較小，只可能是0!~9!的數字和，所以可以直接用dfs搜索。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
int sum;
bool vis[11];
map<int,int>mymap;
void dfs(int n)
{
if(n==10)
{
if(mymap.find(sum)==mymap.end())mymap[sum]=1;
return;
}
sum+=a[n];
dfs(n+1);
sum-=a[n];
dfs(n+1);
}
int main()
{
memset(vis,false,sizeof(vis));
sum=0;
mymap.clear();
dfs(0);
int n;
while(~scanf("%d",&n))
{
if(n<0)break;
if(n==0||mymap.find(n)==mymap.end())puts("NO");
else puts("YES");
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
int sum;
bool vis[11];
map<int,int>mymap;
void dfs(int n)
{
if(n==10)
{
if(mymap.find(sum)==mymap.end())mymap[sum]=1;
return;
}
sum+=a[n];
dfs(n+1);
sum-=a[n];
dfs(n+1);
}
int main()
{
memset(vis,false,sizeof(vis));
sum=0;
mymap.clear();
dfs(0);
int n;
while(~scanf("%d",&n))
{
if(n<0)break;
if(n==0||mymap.find(n)==mymap.end())puts("NO");
else puts("YES");
}
return 0;
}
