主題

ZeroJudge - d423: 10856 - Recover Factorial 解題心得

Not In My Back Yard | 2018-12-17 22:44:13 | 巴幣 0 | 人氣 437

題目連結:


題目大意:
階乘可以寫作一連串的質數相乘,例如 4!=2 × 2 × 2 × 3 ,有「4個」質因數。

現給定一正整數 N ( 0 ≦ N ≦ 10, 000, 001 ),請找出 X! 之質因數個數為 N 個的最小可能之 X 為何?若不存在這樣子的 X ,請輸出「Not possible.」



範例輸入:
4
240
241
-1



範例輸出:
Case 1: 4!
Case 2: 101!
Case 3: Not possible.



解題思維:
仔細觀察質因數個數的成長: 1!,0 個; 2!,1 個; 3!,2 個; 4!,4 個……很明顯就只是一直加下一個數字的質因數個數。因此我們可以利用這樣子的特性去建表。

當然,在為每個整數求質因數的個數之前也要先建一個質數表。可以用埃式篩法加快建質數表的速度,這方法可以在我之前的一些關於質數的程式碼裡也可見到。

然後,再用大家應該耳熟能詳的 O(sqrt(N)) 的方法(原理跟檢查是否為質數,幾乎一樣)為每個數字找出質因數個數。

然後開一個陣列大小為 10, 000, 001 ,每個索引值本身代表質因數的個數。因此第0個位置為0,第一個位置為2,第二個位置因為找不到所以設為 -1……以此類推。

最後,在輸入的時候,輸入進什麼數字就到上述的陣列去尋找。對應位置不是 -1 的就輸出儲存的值;反之,輸出「Not Possible」。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作