POJ 1150 ——The Last Non-zero Digit(數(shù)論)

題意很簡單，要求你求出一個排列數(shù)P(n,m)中最后一個非0的數(shù)字.
由于n的數(shù)值巨大，想直接求出來恐怕是不可行的。
在網(wǎng)上有這樣一個英文的解題報(bào)告，由于缺少中文的資料，硬著頭皮把它看完了:-)

The first program

Consider the number N! factored into product of powers of prime numbers. It means N!=2ⁱ * 3^j * 5^k * 7^l * ... 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! / (2^k * 5^k). Therefore we can compute the result using the equation:

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 2^a * 5^b where a and b are the highest numbers such that the i is divisible by this product. Number (N! / (2ⁱ * 5^k)) 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 (2^i-k mod 10 * f(N!) ) mod 10. Numbers i and k are computed much more efficiently. More precisely

(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 2^i-k mod 10. Observe, that

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 2^i-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 3^a mod 10, 7^b mod 10, 9^c mod 10 in the similar way as we did for 2^i-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(N²) 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=2^a * 5^b). 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.



這個題怎么來做呢？先別急，我們先來討論一下下面幾個子問題：
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這個質(zhì)因數(shù)只在5的倍數(shù)里面才出現(xiàn)，所以我從5，10，15中各抽出一個5，這相當(dāng)于有15/5個質(zhì)因數(shù)5,之后5，10，15就變成了1，2，3；
由于非5的倍數(shù)顯然不在考慮范圍之內(nèi)，所以我們只需繼續(xù)討論它的子問題3！即可。
這樣，我們可以用遞歸來解決這個問題。有了這個方法，我們是不是能夠輕易地解決n!末尾有多少個0呢？想想看...n!后0的個數(shù)是不是就和某個質(zhì)因數(shù)的個數(shù)有關(guān)呢？^_^
比如說，我們要求5出現(xiàn)的次數(shù)，可以這樣寫：

 2.如何求出n!階乘最后非0位？
比如說我們要找10!最后非0位，由于質(zhì)因數(shù)2和5組合之后會使得末尾產(chǎn)生0.那么我們不妨把10！中2，5質(zhì)因數(shù)全部去掉，（但是請注意2的數(shù)目其實(shí)比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因子已經(jīng)被去除，那么剩下的數(shù)字末尾一定是3，7，9，1中四者之一。然后我們再求出這么一串?dāng)?shù)相乘以后末尾的數(shù)是幾.最后再補(bǔ)上2對末位的影響即可！

總結(jié)一下，求10!最后一個非0位的步驟如下：
step1：首先將10!中所有2，5因子去掉；
step2：然后求出剩下的一串?dāng)?shù)字相乘后末尾的那個數(shù)。
step3：由于去掉的2比5多，最后還要考慮多余的那部分2對結(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是個難點(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ù)了；

一個數(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中的個數(shù)也就是1 2 3 4 5中的個數(shù)，也就是說我們又把這個問題劃分成了一個原來問題的子問題。

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ì)這個數(shù)列中末尾為x（1，3，7，9）的個數(shù)可以這樣寫：g(n,x) = n/10+(n%10 >= x)+g(n/5,x) 

這樣利用了兩個遞歸方程，我們就可以在lgn的時間內(nèi)計(jì)算出末尾為1,3,7,9的數(shù)的個數(shù)了

好了，現(xiàn)在我們得到了這串?dāng)?shù)字中末尾是3，7，9的數(shù)字的個數(shù)，我們利用循環(huán)節(jié)的性質(zhì)可以快速地算出這串?dāng)?shù)字相乘后mod 10的結(jié)果，在考慮下當(dāng)時多除的2(其實(shí)也可以用循環(huán)節(jié)來處理），便可求出答案！




解決了上面兩個子問題，我想求P(n,m)最后一個非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，這里還要注意一個trick,就是2的出現(xiàn)次數(shù)如果小于5，（這對于排列數(shù)來說是可能的）我們可以直接輸出5，如果2的數(shù)目等于5，那么2的循環(huán)節(jié)不需要考慮。至于3，7，9的循環(huán)節(jié)，由于這些數(shù)的4次方末位剛好是1，所以就不需要特殊考慮了。


附代碼：

                                                                                                                                                                                                         special thanks to 星星 

posted on 2009-10-31 19:07 abilitytao 閱讀(3619) 評論(8)  編輯 收藏 引用