題意很簡(jiǎn)單，要求你求出一個(gè)排列數(shù)P(n,m)中最后一個(gè)非0的數(shù)字.
由于n的數(shù)值巨大，想直接求出來(lái)恐怕是不可行的。
在網(wǎng)上有這樣一個(gè)英文的解題報(bào)告，由于缺少中文的資料，硬著頭皮把它看完了:-)
The first program
Consider the number N! factored into product of powers of prime numbers. It means N!=2i * 3j * 5k * 7l * ... Note, that for each N>1 the power i is greater than k. It means, that the last non-zero digit of N! is the same as the last digit of N! / (2k * 5k). Therefore we can compute the result using the equation:
(N! / (2k * 5k)) mod 10 = ((N! / (2i * 5k)) mod 10 * 2i-k mod 10) mod 10
Number i can be obtained easily - we will divide each a=1,2,...,N by 2 until the resulting number is not divisible by 2 and after each division we will add one to the variable i. Number k can be obtained in the same manner. Let f(i) denotes the number which we obtain by dividing i by the 2a * 5b where a and b are the highest numbers such that the i is divisible by this product. Number (N! / (2i * 5k)) mod 10 is equal to f(N!) mod 10 and can be computed as f(1) * f(2) * ... * f(N) mod 10. We will perform operation mod 10 after each multiplication in order to keep the resulting number as small as possible.
The advantege of this approach is that we do not need to implement arithmetics of large numbers. Some ideas used here are used in the second, more efficient program, as well.
The second program
The second program also computes the result as (2i-k mod 10 * f(N!) ) mod 10. Numbers i and k are computed much more efficiently. More precisely
i=N div 2 + (N div 2) div 2 + ((N div 2) div 2) div 2 + ...
(We get zero after finite number of divisions.) Number k can be computed in the same way. After that we can compute i-k and we need to find 2i-k mod 10. Observe, that
21 mod 10 = 2, 22 mod 10 = 4, 23 mod 10 = 8, 24 mod 10 = 6, 25 mod 10 = 2, 26 mod 10 = 4, ...
i.e. the period is 4 and we need only to compute (i-k) mod 4 and then to find corresponding last digit. This observation can help us to simplify computation of i and k - we do not need their exact values (that can be long) but we need only (i-k) mod 4.
We have shown how to compute 2i-k mod 10. Now let us consider f(N!) mod 10 = ((f(1) mod 10) * (f(2) mod 10) * ... * (f(N) mod 10)) mod 10. Note, that f(i) mod 10 is always 1,3,7 or 9. If we knew, how many 3,7,9 are among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10), we could compute 3a mod 10, 7b mod 10, 9c mod 10 in the similar way as we did for 2i-k (last digits of powers of 3,7,9 are also periodical).
To compute the number of 3,7,9 among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10) is not so easy. We will divide numbers 1,2,...,N into groups so, that in each group are numbers with same quotient i/f(i) and we will compute number of 3,7,9 among (f(i) mod 10) for each such group separatelly (there are O(N2) such groups). First, let us consider a group in which i/f(i)=1. This is the group of all numbers not divisible by 2 and 5. The number of 3,7,9 in this group is the same as number of 3,7,9 among 1 mod 10, 2 mod 10, ..., N mod 10. This number can be counted easily - it is N div 10 + a where a is 1 if the last digit of N is at least 3 (resp. at least 7 or at least 9). Now let us consider a group in which i/f(i)=L (where L=2a * 5b). We obtain this group by taking each L-th number from the sequence 1,2,3,... and dividing it by L. It means that number of 3,7,9 for this group will be the same as the number of 3,7,9 among 1 mod 10, 2 mod 10, ..., (N div L) mod 10.
Now we know everything we needed for construction of a program. Since numbers in the input file are long, we need to implement arithmetics for long numbers. However, by careful implementation we can achieve that only division of a long number by small integer is necessary.
這個(gè)題怎么來(lái)做呢？先別急，我們先來(lái)討論一下下面幾個(gè)子問題：
1.如何求出n階乘中質(zhì)因數(shù)x(比如說5）出現(xiàn)的次數(shù)？
比如說15的階乘 ：1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
由于5這個(gè)質(zhì)因數(shù)只在5的倍數(shù)里面才出現(xiàn)，所以我從5，10，15中各抽出一個(gè)5，這相當(dāng)于有15/5個(gè)質(zhì)因數(shù)5,之后5，10，15就變成了1，2，3；
由于非5的倍數(shù)顯然不在考慮范圍之內(nèi)，所以我們只需繼續(xù)討論它的子問題3！即可。
這樣，我們可以用遞歸來(lái)解決這個(gè)問題。有了這個(gè)方法，我們是不是能夠輕易地解決n!末尾有多少個(gè)0呢？想想看...n!后0的個(gè)數(shù)是不是就和某個(gè)質(zhì)因數(shù)的個(gè)數(shù)有關(guān)呢？^_^
比如說，我們要求5出現(xiàn)的次數(shù)，可以這樣寫：
int get5(int n)//計(jì)算n!中質(zhì)因子5的出現(xiàn)次數(shù)
{
if(n==0)
return 0;
return n/5+get5(n/5);
}
2.如何求出n!階乘最后非0位？
比如說我們要找10!最后非0位，由于質(zhì)因數(shù)2和5組合之后會(huì)使得末尾產(chǎn)生0.那么我們不妨把10！中2，5質(zhì)因數(shù)全部去掉，（但是請(qǐng)注意2的數(shù)目其實(shí)比5的要多，所以我們要在最后考慮多余的2對(duì)末位的影響）
如 1*2*3*4*5*6*7*8*9*10 去掉2 ，5 因子后 就是1*1*3*1*1*3*7*1*9*1，由于2，5因子已經(jīng)被去除，那么剩下的數(shù)字末尾一定是3，7，9，1中四者之一。然后我們?cè)偾蟪鲞@么一串?dāng)?shù)相乘以后末尾的數(shù)是幾.最后再補(bǔ)上2對(duì)末位的影響即可！
總結(jié)一下，求10!最后一個(gè)非0位的步驟如下：
step1：首先將10!中所有2，5因子去掉；
step2：然后求出剩下的一串?dāng)?shù)字相乘后末尾的那個(gè)數(shù)。
step3：由于去掉的2比5多，最后還要考慮多余的那部分2對(duì)結(jié)果的影響。
step4：output your answer!
正如上面文章里所說的“To compute the number of 3,7,9 among (
f(1) mod 10), (
f(2) mod 10), ..., (
f(N) mod 10) is not so easy”，這里面步驟2是個(gè)難點(diǎn)。如何求出剩下的這串?dāng)?shù)字相乘后最后一位是幾呢？這可以轉(zhuǎn)化成求出這些數(shù)里面末尾是3，7，9的數(shù)字出現(xiàn)的次數(shù)（為啥？因?yàn)檫@些數(shù)的n次方是有規(guī)律的，周期為4，不信你可以推一下）
好，現(xiàn)在問題就是如何求出這串?dāng)?shù)字中末尾3，7，9各自出現(xiàn)的次數(shù)了；
一個(gè)數(shù)列實(shí)際上可以分成偶數(shù)列和奇數(shù)列，以1*2*3*4*5*6*7*8*9*10為例
分成1 3 5 7 9, 2 4 6 8 10
這樣我們嘗試分別進(jìn)行統(tǒng)計(jì)，可以發(fā)現(xiàn)，實(shí)際上2，4，6，8，10中的個(gè)數(shù)也就是1 2 3 4 5中的個(gè)數(shù)，也就是說我們又把這個(gè)問題劃分成了一個(gè)原來(lái)問題的子問題。
f(n) = f(n/2) + g(n),g(n)表示奇數(shù)列中的數(shù)目，所以我們需要解決g(n)
再次觀察g(n)
實(shí)際上又分成了兩部分1 3 7 9 11 13 17 19 21。。。以及5的奇倍數(shù)5，15，25。。。說明又出現(xiàn)了子問題,如果要統(tǒng)計(jì)這個(gè)數(shù)列中末尾為x（1，3，7，9）的個(gè)數(shù)可以這樣寫：g(n,x) = n/10+(n%10 >= x)+g(n/5,x)
這樣利用了兩個(gè)遞歸方程，我們就可以在lgn的時(shí)間內(nèi)計(jì)算出末尾為1,3,7,9的數(shù)的個(gè)數(shù)了
好了，現(xiàn)在我們得到了這串?dāng)?shù)字中末尾是3，7，9的數(shù)字的個(gè)數(shù)，我們利用循環(huán)節(jié)的性質(zhì)可以快速地算出這串?dāng)?shù)字相乘后mod 10的結(jié)果，在考慮下當(dāng)時(shí)多除的2(其實(shí)也可以用循環(huán)節(jié)來(lái)處理），便可求出答案！
解決了上面兩個(gè)子問題，我想求P(n,m)最后一個(gè)非0位就變得十分容易了。
P(n,m)實(shí)際上等于 n! / (n-m)!
我們可以求出n! 和(n-m)!中質(zhì)因數(shù)2，5，3，7，9分別出現(xiàn)的次數(shù)，然后再各自相減。
然后再用循環(huán)節(jié)處理，即可！
BTW，這里還要注意一個(gè)trick,就是2的出現(xiàn)次數(shù)如果小于5，（這對(duì)于排列數(shù)來(lái)說是可能的）我們可以直接輸出5，如果2的數(shù)目等于5，那么2的循環(huán)節(jié)不需要考慮。至于3，7，9的循環(huán)節(jié)，由于這些數(shù)的4次方末位剛好是1，所以就不需要特殊考慮了。
附代碼：
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int get2(int n)//計(jì)算n!中質(zhì)因子2的出現(xiàn)次數(shù)
{
if(n==0)
return 0;
return n/2+get2(n/2);
}
int get5(int n)//計(jì)算n!中質(zhì)因子5的出現(xiàn)次數(shù)
{
if(n==0)
return 0;
return n/5+get5(n/5);
}
/**///////////////////////////////////////////////////////////////////////////int g(int n,int x)//計(jì)算f(1) to f(n) 中，奇數(shù)數(shù)列中末尾為x的數(shù)出現(xiàn)的次數(shù)
{
if(n==0)
return 0;
return n/10+(n%10>=x)+g(n/5,x);
}
int getx(int n,int x)//計(jì)算f(1) to f(n)中，末尾為x的數(shù)的出現(xiàn)次數(shù)
{
if(n==0)
return 0;
return getx(n/2,x)+g(n,x);
}
/**///////////////////////////////////////////////////////////////////////////
int table[4][4] =
{
6,2,4,8,//2^n%10的循環(huán)節(jié)，注意如果2的個(gè)數(shù)為0時(shí)候，結(jié)果應(yīng)該是1，要特殊處理。
1,3,9,7,//3
1,7,9,3,//7
1,9,1,9,//9
};//3，7，9的循環(huán)節(jié)中第一位，剛好是1，故不需要考慮這些數(shù)字出現(xiàn)次數(shù)為0的情況。
int main()
{
int n,m;
int num2;
int num3;
int num5;
int num7;
int num9;
while(scanf("%d%d",&n,&m)!=EOF)
{
num2=get2(n)-get2(n-m);
num5=get5(n)-get5(n-m);
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 res=1;
if(num5>num2)
{
printf("5\n");
continue;
}
else
{
if(num2!=num5)
{
res*=table[0][(num2-num5)%4];
res%=10;
}//如果num2==num5,那么2^0次方mod 10應(yīng)該為1 ，而不是table中的6,所以要特殊處理。
res*=table[1][num3%4];
res%=10;
res*=table[2][num7%4];
res%=10;
res*=table[3][num9%4];
res%=10;
}
printf("%d\n",res);
}
return 0;
}
special thanks to
星星