UVa 10212

網址

http://uva.onlinejudge.org/external/102/10212.html

NPM = N * (N-1) * (N-2) * … * (N-M+1)

請問 NPM 的非0位數最右邊 D 為何？

例如：if NPM = 5036300, 則D為 3

0 <= N <= 20000000 M <= N

每一行為一個測資 N, M

end by EOF

每一個測資輸出一行, D

我們可以知道答案為 N!/(N-M)! 的 D 值，所以我們要分別計算 N! 和 (N-M)!

我們先討論數字 2,5 相乘，1 個 2 乘上 1 個 5 就會變成 10, D 值就會是 1 乘上其他數字

所以只要找 N! 有幾個 2, 5 相乘，找的方法如下

2的個數 = 2 的倍數 + 4 的倍數 + 8 的倍數… 可以寫成 num2[N] = N/2 + num2[N/2]; 轉換成 function 會比較好寫

5的個數依此類推。

求出來後可以分成 3 種 Case

Case1: 5 的個數 > 2 的個數，則 D 一定為 5，因為 5 乘上奇數一定還是 5 ← 答案

Case2: 5 的個數 = 2 的個數，則 D 不用去考慮。

Case3: 5 的個數 < 2 的個數，則要考慮剩餘 2 相乘的情況，

2 相乘會有一個循環 2 4 8 6，又回到2，4個數字一個循環，有循環的部分建議可以建 table

接下來算 1, 3, 7, 9 的個數 ( 1 可以忽略 )

這邊分成 3 種 case 加種

Case1: 我們先看奇數列 ( 先排除 5 的倍數 ) || 1, 3, 7, 9, || 11, 13, 17, 19, || 21, …

可以發現到是以 10 的倍數為一單位再循環，所以我們可以先算 N/10 代表有幾個 3 ( 之後以 3 為例子 7, 9 依此類推 )

記得要加上 N % 10 >= 3 ，因為 N 不一定是 10 的倍數

Case2: 我們觀察5的倍數而且是奇數

===== ===== ===== ===== ===== 5, 15, 25, 35, … 除以5之後會變成 ===== ===== ===== ===== ===== 1, 3, 5, 7, …
===== ===== ===== ===== =====

又變成 Case1 的情況，所以 Case2 只要算 N/5的 Case1 情況就好。

Case3: 最後來看偶數列

=== === === === === === === 2, 4, 6, 8, 10, 12, 14 除以 2 之後會變成 === === === === === === === 1, 2, 3, 4, 5, 6, 7 === === === === === === ===

又可以轉換成 Case1 + Case2 的情況，所以 Case3 只要算 N/2 的 Case1 + Case2 就好

整合以上 3 種 Case 會變成 num3[N] = num3[N/2] + numodd3[ N/10 + N%10 >=3 + numodd3[N/5] ] 同樣轉換成 2 個 function 會比較好寫

取得 3, 7, 9 的個數之後，我們也可以發現到這三個數同 2 也是 4 個一循環

3: 3 9 7 1

7: 7 9 3 1

9: 9 1 9 1

事實上只要 2, 3, 7, 9 建立一個循環 table 就好

D 只要再乘上 3 的個數 %4 , 乘上 7 的個數 %4 , 乘上 9 的個數 %4 的 table 值 ( 2 前面已算過 )

D 最後記得 %10，D最後不可能是 0 了，因為 2 已經沒有 5 可以匹配。

以上！