題目都一樣，所以這裡一起解說
首先是階乘的定義：設一個正整數 n ，符號 n！代表從1開始依正整數順序連乘到 n
即 n！= 1 x 2 x 3 x ...... x n，而為了計算上的方便，定義 0！= 1，接著就是題目所要求的，給定一正整數 n，求 n！當中從個位數起算，第一個遇到的非零位的數字為何？例如 n = 10，10！= 3628800，從個位數往前找，第一個非零位數字是 8，很顯然的，解題不可能使用暴力法直接連乘，因為題目測資非常非常大，將測資給定的數字使用階乘，會遠遠超過一般存儲數字的上限，因此必須改以「找規律」的方式解題。(題外話，大部分題目都是要找規律)
這裡不妨先思考題目要求的 "第一個非零位數字"，階乘是從 1 開始連續一段自然數相乘，2！、3！、4！尾端都沒有 0，從 5！開始就出現第一個 0，而第二個 0 是要到 10！才出現，尾端的 0 代表 10 倍，而
10 = 2 x 5，也就是說 n！尾端有幾個 0，就代表將 n！質因數分解後，質因數 5 的次方數，而在有限大的 n 以內，是 2 的倍數的自然數一定比是 5 的倍數的自然數多，因此 n！內所有的 5 都與 2 相乘變成了尾端的 0，也就是說尾數是 5 的自然數不會影響第一個非零位。因此我們可以令 n！= 2^a * 5^b * c，其中
a、b、c都是整數且 c 與 2、5 互質，由剛剛的推理可以知道 5 不影響尾數變化，那麼剩下的部分
2^(a-b) * c，就是造成尾數變化的原因。
尾數變化看似雜亂無章，但如果我們把相同尾數的質因數看作一個群體，觀察相同尾數相乘之後的樣子，
或許可以找到一些規律，以下是 1 ~ 9 的次方數表格：
從指數中觀察規律：
(一) 1 不論怎麼乘都是 1，所以尾數是 1 的質因數 ( 11、31、41... ) 不影響 n！第一個非零位數字
(二) n！在質因數分解之後，除了 2 其他質因數都是奇數，所以原本尾數4、6、8的自然數都不需考慮，
僅僅只考慮 2 即可
(三) 5 不影響非零位，上面已經解釋了
(四) 觀察 2、3、7、9 次方的尾數，能明顯發現 2、3 跟 7 每 4 個循環一次，9 每 2 個循環一次：
(1) 2 的循環節：2 > 4 > 8 > 6
(2) 3 的循環節：3 > 9 > 7 > 1
(3) 7 的循環節：7 > 9 > 3 > 1
(4) 9 的循環節：9 > 1
不論題目測資有多大，我們都不需要去逐一列出每個質數後再分析尾數，而是直接將相同尾數看作一個群體，直接算這群體含有幾個數字，將 n！轉化成 ( 尾數 ) ^ (個數)，再利用循環節就能快速求解了。
我們知道 9 = 3^2，代表說乘一次尾數 9 的結果會等價於乘兩次尾數 3，然後觀察 3 跟 7 的循環節，運用一點技巧我們得知
( n 是自然數 )，這裡使用了 "同餘" 的概念，
( n 是自然數 )，這裡使用了 "同餘" 的概念，同餘簡單說就是在三等號的左右兩邊的數字，在分別除以同一個數字後會有相同的餘數，這式子用術語來講就是 " 3^n 與 7^(3n) 對模 10 同餘 "，某數除以10 的餘數恰好是某數的最後一位數字，運用技巧做出來的上述式子是為了讓 3 與 7 的循環節內容一致，從而使乘一次尾數 3 的結果會等價於乘三次尾數 7 ( 可以自己手動帶入 n 的值，用上面的表去對照 )，我們就成功將影響 n！第一個非零位的數字壓縮到剩下 2 跟 7 了。
綜上所述，我們在 1 ~ n 之間，針對每一個正整數提出全部的 2 跟 5 後，在剩餘部分裡分別統計尾數 3、7、9 出現次數，然後利用 "同餘" 的概念，快速解出多個2、3、7、9 自乘後的尾數為何，最後相乘取其尾數即得到答案。
用文字敘述實在非常難解釋解題的思路，以下直接使用範例 123！，來求題目要求的答案：
(一) 首先是處理 5，統計一個階乘能分解幾個 5，只要算這一連續的自然數當中有幾個 5 的倍數就好，
1 ~ 123 中有幾個 5 的倍數，很簡單，回憶除法的最初始定義，將 1~123 依自然順序每 5 個為一組，
1~5、6~10、......、116~120、121~123，一共有123 / 5 = 24 組 ( 餘數在程式運算過程會自動捨棄 )
這 24 組中都恰好只有一個數字是 5 的倍數，但我們知道這些數字當中還有 5 的倍數，於是我們將這
24 組中的 5 的倍數拿出來，依自然順序再分組，一共有 24 / 5 = 4 組，意思是 24個 5的倍數中，
還有 4個能再提出一個 5 出來的數字，也就是 25、50、75、100，下面用圖表來說明這一段：
在第二次分組中能發現，數字在提出 5 之後，尾數發生了改變，由先前提到的我們只關注尾數是 2、
3、7、9 (偶數部分暫不處理) 的部分，但是在提出 5 的過程中這些數字才出現，代表在統計 5的倍數
過程能一併統計尾數 3、7、9的數字有多少，除了 5 的倍數，還有 2 的倍數需要處理，但有數字既是
2 的倍數也是 5 的倍數，這裡我們寫程式只要使用雙重迴圈就可以解決。分組只要進行 2 次就能得到
123！中一共有 24+4 = 28 個 5 連乘，2 的倍數也是同樣的方法，可以得到
別忘了在程式中除法會自動刪除無法除盡的餘數，所以我們知道 123！中有 117 個 2 連乘，寫成數學
式 : 123！= 2^117 * 5^28 * c，接著就是統計尾數 3、7、9的數字了。
(二) 尾數 3、7、9的數字該怎麼統計呢，一樣以範例 123！來分析，我們現在使用的數字是 10 進位，從
自然數 1 開始一個一個數，數到十後數字會寫成 10，這些數字當中，尾數 3、7、9 數字都恰只出現
一次，接著從 11 數到 20，尾數 3、7、9 數字同樣恰只出現一次 (13、17、19 )，依此類推一直到
121 ~ 123，此時只有尾數 3 數字 123 而沒有尾數 7、9，因此我們統計出尾數 3 數字出現了
3、13、23、......、113、123 共 12 + 1 = 13 個，尾數 7、9 則各 12 個，前面說過我們不需要在意
這個數字的全貌，只在意個位數就好，因此我們就把 (一) 結尾的 c 直接看成 3^x * 7^y * 9^z，因此
到目前統計 x = 13，y = z = 12。接下來要提出 2 跟 5 繼續統計，以下用圖表表示：
經過完整分析之後，尾數 3 的數字有 33 個，尾數 7 的數字有 26 個，尾數 9 的數字有 25 個，於是
我們的 c 就可以改寫成 3^33 * 7^26 * 9^25。
(三) 由(一)(二)我們將 123！改寫成 2^117 * 5^28 * 3^33 * 7^26 * 9^25，首先每一個 5 能與一個 2 相乘，
變成123！尾端的 0，消去所有的 5 後剩下 2^89 * 3^33 * 7^26 * 9^25，接著因為循環節，可以得知
89 ≡ 1 (mod 4)，也就是 2^89 ≡ 2^1 (mod 10)，然後 9^25 = 3^50，則尾數 3 有 33+50 = 83 個，再
接著 3^83 ≡ 7^(3*83) (mod 10)，則尾數 7 有 26+83*3 = 275 個，觀察尾數 7 的循環( 對照上面 )，
275 ≡ 3(mod 4)，也就是 7^275 ≡ 7^3 ≡ 3 ( mod 10 )，最終可得123！≡ 2*3 ≡ 6 ( mod 10 )，因此
123！的第一個非零位數字是 6。演算過程如下：
至此，我們能使用這方法對任意大的自然數 n 的階乘 ( n！) 求第一個非零位數字，最後附上我的程式碼
| import java.io.*; public class D715 { public static void main(String[] args) throws IOException { MyReader reader = new MyReader(System.in); //我自己寫的class，這邊就賣關子不打 PrintWriter prt = new PrintWriter(new BufferedOutputStream(System.out)); int mod2, mod7; long n, tmp, front10, mod10; long last2, last3, last5, last7, last9; long[] last10 = {1L, 1L, 2L, 6L, 4L, 2L, 2L, 4L, 2L, 8L, 8L}; while(reader.hasNext()) { n = reader.nextLong(); if(n <= 10L) { prt.println(last10[(int)n]); continue; } mod2 = mod7 = 0; last2 = last3 = last5 = last7 = last9 = 0L ; tmp = n; while(tmp > 1) { last5 += tmp/5; tmp/= 5; } tmp = n; while(tmp > 1) { for(long t = tmp ; t > 0 ; t/= 5) { front10 = t/10 ; mod10 = t%10 ; last3 += front10 + (mod10 >= 3L ? 1 : 0); last7 += front10 + (mod10 >= 7L ? 1 : 0); last9 += front10 + (mod10 >= 9L ? 1 : 0); } last2 += tmp/2; tmp/= 2; } last2 -= last5; last2 %= 4; last3 += last9*2; last7 += last3*3; last7 %= 4; switch((int)last2) { case 1: mod2= 2; break; case 2: mod2= 4; break; case 3: mod2= 8; break; case 0: mod2= 6; break; } switch((int)last7) { case 1: mod7= 7; break; case 2: mod7= 9; break; case 3: mod7= 3; break; case 0: mod7= 1; break; } prt.println(mod2*mod7%10); } prt.flush(); } } |
----------------------------------------------------------------------------------------------------------------------------------------
我打了超級多又非常仔細，因為我笨(X
解法參考來源是下面這行，光看他的我看很久才懂.........
http://rchardx.is-programmer.com/posts/14751.html
達人
