版本 d09df91308dd4fa7ebe590540f8c16183ddae2d0
Changes from beginning to d09df91308dd4fa7ebe590540f8c16183ddae2d0
---
title: UVa 10212
toc: no
categories: 題解 數論
...
網址
====
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
Technique details
=================
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 可以匹配。
以上！
