主題

ZeroJudge - d636: 大爆炸bomb 解題心得

Not In My Back Yard | 2021-03-25 03:00:01 | 巴幣 0 | 人氣 54

題目連結:


題目大意:
輸入只有一列,其給定兩正整數 a 、 b(1 ≦ a ≦ 65536,1 ≦ b ≦ 2147483647),試問 a ^ b 之值取除以 10007 之餘數為何?



範例輸入:
2 31


範例輸出:
1462


解題思維:
餘數有一個基本性質——不管先做還是後做運算(在本題為相乘),兩者結果同餘。

所以像是 (2 ^ 16 mod 10007) × (2 ^ 16 mod 10007) ≡ (2 ^ 16 × 2 ^ 16) mod 10007 ≡ 2 ^ 32 mod 10007 ≡ 2924。

因此我們在做 X × Y 這類操作時,我們可以先計算 X' = X mod 10007 、 Y' = Y mod 10007 ,然後計算 X' × Y',最後再取 10007 的餘數。

因為次方之值可以很大,所以我們需要快速冪,參見這題的中段。加上上面的餘數性質即可快速地求出所求。




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

創作回應

相關創作

更多創作