主題

ZeroJudge - c627: 階乘問題 解題心得

Not In My Back Yard | 2021-11-07 00:00:14 | 巴幣 2 | 人氣 75

題目連結:


題目大意:
輸入有多列(不超過 20 列),每列給定一正整數 N(N < 10 ^ 300),請輸出 N!(即 N 階乘)對 10 ^ 9 + 7 取餘數後的結果。



範例輸入:
2
3
15


範例輸出:
2
6
674358851


解題思維:
(以下稱 10 ^ 9 + 7 為 P)
可以看到當 N ≧ P 時,其結果將都一定會是 0。因為此時 N! 將含有 P 這個數字作為因數之一,因此根據模運算的定義,其餘數為 0。所以當輸入的數字 ≧ P 時,直接輸出 0 即可。

對於 N < P 的情況,由於 P 為一質數,所以可以先使用威爾遜定理(Wilson's Theorem)將問題大小縮減至一半,如下:
根據該定理可知
(P - 1)! ≡ -1 (mod P)
也就是當 N = P - 1 時,餘數之值恰好為 P - 1。而當 N 不為 P - 1 時,我們可以將 N! 改寫為
(P - 1)! × (P - 1) 的模反元素 × (P - 2) 的模反元素 × …… × (N + 1) 的模反元素
而兩者同餘。

因此可以看到當 P - N - 1 為偶數時,N! 與 (P - 1) × (P - N - 1)! 同餘;反之為奇數時,N! 與 (P - N - 1)! 同餘。這樣我們只需要知道 0! ~ P'! 的值即可,其中 P' = floor(P ÷ 2)。

接著我們可以利用這題求階乘之值的方式來預先建表。而本題因為輸入的數字很少,而數字範圍很大,所以從 0! 跑到 P'! 還是需要不少時間。因此我們可以定義 S = 5000001,我們直接在本地端先跑一次求出 0! ~ P'! 之值然後從 0! 開始每 S 個輸出該時刻的階乘值,而這樣會出現 100 個值。

接著我們就直接把這 100 個值直接複製到程式碼中存為一陣列,接著按照原本的方式求得對應的 N! 之值即可。




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

創作回應

相關創作

更多創作