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

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

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階乘中質因數x(比如說5）出現的次數？
比如說15的階乘 ：1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
由于5這個質因數只在5的倍數里面才出現，所以我從5，10，15中各抽出一個5，這相當于有15/5個質因數5,之后5，10，15就變成了1，2，3；
由于非5的倍數顯然不在考慮范圍之內，所以我們只需繼續討論它的子問題3！即可。
這樣，我們可以用遞歸來解決這個問題。有了這個方法，我們是不是能夠輕易地解決n!末尾有多少個0呢？想想看...n!后0的個數是不是就和某個質因數的個數有關呢？^_^
比如說，我們要求5出現的次數，可以這樣寫：

 2.如何求出n!階乘最后非0位？
比如說我們要找10!最后非0位，由于質因數2和5組合之后會使得末尾產生0.那么我們不妨把10！中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對末位的影響即可！

總結一下，求10!最后一個非0位的步驟如下：
step1：首先將10!中所有2，5因子去掉；
step2：然后求出剩下的一串數字相乘后末尾的那個數。
step3：由于去掉的2比5多，最后還要考慮多余的那部分2對結果的影響。
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是個難點。如何求出剩下的這串數字相乘后最后一位是幾呢？這可以轉化成求出這些數里面末尾是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（1，3，7，9）的個數可以這樣寫：g(n,x) = n/10+(n%10 >= x)+g(n/5,x) 

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

好了，現在我們得到了這串數字中末尾是3，7，9的數字的個數，我們利用循環節的性質可以快速地算出這串數字相乘后mod 10的結果，在考慮下當時多除的2(其實也可以用循環節來處理），便可求出答案！




解決了上面兩個子問題，我想求P(n,m)最后一個非0位就變得十分容易了。
P(n,m)實際上等于 n! / (n-m)!
我們可以求出n! 和(n-m)!中質因數2，5，3，7，9分別出現的次數，然后再各自相減。
然后再用循環節處理，即可！
BTW，這里還要注意一個trick,就是2的出現次數如果小于5，（這對于排列數來說是可能的）我們可以直接輸出5，如果2的數目等于5，那么2的循環節不需要考慮。至于3，7，9的循環節，由于這些數的4次方末位剛好是1，所以就不需要特殊考慮了。


附代碼：

                                                                                                                                                                                                         special thanks to 星星 

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