求n!，C(n,m)，A(n,m)最后的非零位。

?

先說說怎樣求n!最后的非零位吧！

比如找10！最后的非零位，由于質因數2和5的組合之后末尾會產生0，所以我們先把2，5的質因子全部去掉，由于2的數目要比5多，所以我們要在最后考慮

多余的2對末尾的影響。

比如：1*2*3*4*5*6*7*8*9*10去掉2，5的因子后就是：

1*1*3*1*1*3*7*1*9*1，由于去掉了2，5，那么剩下的數字末尾一定是3，7，9，1四者之一，然后我們再求出這么一串數相乘以后末尾的數是幾，最后再補上

2對末位的影響即可。

所以，求n！最后非零位分為4步：

(1)將n！中所有的2，5因子去掉

(2)求出剩下的一串數字相乘后末尾的那個數

(3)由于2比5多，考慮多余的2對結果的影響

(4)輸出答案

對于步驟(1)，直接計算去除就行了，很簡單。

對于步驟(2)，是難點，這個問題可以轉化為求出這些數里面末尾是3，7，9的數字出現的次數，因為這些數的n次方是有規律的，周期為4.

現在的問題就是如何求出這串數字末尾3，7，9各自出現的次數了。

一個數列實際上可以分為偶數列和奇數列。

例如：1*2*3*4*5*6*7*8*9*10

分成：1，3，5，7，9和2，4，6，8，10兩部分

這樣我們嘗試分別進行統計，可以發現，實際上2，4，6，8，10中的個數也就是1，2，3，4，5中的個數，也就是說我們又把這個問題劃分成了一個原來問

題的子問題。

f(n)=f(n/2)+g(n)，g(n)表示奇數列中的數目，我們需要解決g(n)，再次觀察g(n)，實際上又分成了兩部分：1，3，7，9，11，13，17，19，21....................

以及5的奇倍數5，15，25，........

說明又出現了子問題。

如果要統計這個數列中末尾為x(x為1，3，7，9)的個數可以這樣寫：

g(n,x)=n/10+(n%10>=x)+g(n/5,x)

這樣利用了兩個遞歸方程，我們可以在logn的時間內計算出末尾為1，3，7，9的數的個數了

在得到這串數字中末尾是3，7，9的數字個數后，再利用循環節的性質可以快速求出這串數字相乘后mod10的結果，再考慮當時多余的2，便可以求出答案。

知道了這個之后，求A(n,m)就不難了。

先求出n！和(n-m)!中2，5，3，7，9分別出現的次數，然后各自相減，再用循環節處理即可。

這里還要注意一下：2的出現次數如果小于5的出現次數，我們可以直接輸出5，如果2的出現次數等于5的出現次數，那么2的循環節不需要考慮。至于3，

7，9的循環節，由于這些數的4次方末尾剛好為1，所以不需要特殊考慮

?

題目：求A(n,m)最后的非零位數字。題目鏈接：POJ1150

#include <iostream>using namespace std;int GetCount(int n,int x) /**計算n!中質因子x出現的次數*/ {if(n==0) return 0;return n/x+GetCount(n/x,x); }int g(int n,int x) /**計算f(1)到f(n)中奇數數列中末尾為x的數出現的次數*/ {if(n==0) return 0;return n/10+(n%10>=x)+g(n/5,x); }int getx(int n,int x) /**計算f(1)到f(n)中，末尾為x的數的出現次數*/ {if(n==0) return 0;return getx(n/2,x)+g(n,x); }int table[4][4]= {6,2,4,8,1,3,9,7,1,7,9,3,1,9,1,9 };int main() {int n,m;int num2,num3,num5,num7,num9;while(cin>>n>>m){num2=GetCount(n,2)-GetCount(n-m,2);num5=GetCount(n,5)-GetCount(n-m,5);num3=getx(n,3)-getx(n-m,3);num7=getx(n,7)-getx(n-m,7);num9=getx(n,9)-getx(n-m,9);int ans=1;if(num5>num2){cout<<"5"<<endl;continue;}if(num2!=num5){ans*=table[0][(num2-num5)%4];ans%=10;}ans*=table[1][num3%4];ans%=10;ans*=table[2][num7%4];ans%=10;ans*=table[3][num9%4];ans%=10;cout<<ans<<endl;}return 0; }

題目：求C(n,m)最后的非零位數字。題目鏈接：POJ3406

由于m的階乘和n-m的階乘的乘積并不是n的階乘的子集，所以這題要多加一個循環模

#include <iostream>using namespace std;int GetCount(int n,int x) /**計算n!中質因子x出現的次數*/ {if(n==0) return 0;return n/x+GetCount(n/x,x); }int g(int n,int x) /**計算f(1)到f(n)中奇數數列中末尾為x的數出現的次數*/ {if(n==0) return 0;return n/10+(n%10>=x)+g(n/5,x); }int getx(int n,int x) /**計算f(1)到f(n)中，末尾為x的數的出現次數*/ {if(n==0) return 0;return getx(n/2,x)+g(n,x); }int table[4][4]= {6,2,4,8,1,3,9,7,1,7,9,3,1,9,1,9 };int main() {int n,m;int num2,num3,num5,num7,num9;while(cin>>n>>m){num2=GetCount(n,2)-GetCount(n-m,2)-GetCount(m,2);num5=GetCount(n,5)-GetCount(n-m,5)-GetCount(m,5);num3=getx(n,3)-getx(n-m,3)-getx(m,3);num7=getx(n,7)-getx(n-m,7)-getx(m,7);num9=getx(n,9)-getx(n-m,9)-getx(m,9);int ans=1;if(num5>num2){cout<<"5"<<endl;continue;}if(num2!=num5){ans*=table[0][(num2-num5)%4];ans%=10;}ans*=table[1][(num3%4+4)%4];ans%=10;ans*=table[2][(num7%4+4)%4];ans%=10;ans*=table[3][(num9%4+4)%4];ans%=10;cout<<ans<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的求n!,C(n,m)和A(n,m)最后的非零位。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。