#41952:
s10900156@nhsh.tp.edu.tw
(ShanC)
學校
:
臺北市立內湖高級中學
編號 : 138785
來源 : [118.167.202.23]
最後登入時間 ：
2024-11-29 20:43:48
當計算 a^b mod m 時可以把 b 轉成二進位
如此一來當 b 的某一位是 1 時，就可以將 a 乘上 該位的冪次
舉例來說:
在 2^13 中，13 就可以寫成 1101
我們把每一位的 1 拆解開來，並轉成十進位，可以得到 8 + 4 + 1
故推得 2^13 = 2^(8 + 4 + 1) = (2^8) * (2^4) * (2^1)
如此一來，我們只需要用迴圈完成 2 的冪次即可
程式碼:
#define ll long long
ll fpow(ll a, ll b, ll m) {
ll ret = 1;
while (b) {
if (b & 1)
ret = ret * a % m;
b >>= 1;
a = a * a % m;
}
return ret;
}
ZeroJudge Forum