設a,b,c都是正整數，計算a的b次方對c取模（a ^ b % c）在非對稱密鑰演算法RSA中是一個很基本的問題，由于a,b,c可能會比較大，直接計算顯然無法滿足效率要求，可以借鑒快速冪的思想減少計算次數，
做法是根據b的奇偶性，分情況討論：
如果b為偶數，不妨設b = 2k，那么
a ^ b % c
= a ^ 2k % c
= (a ^ k % c) * (a ^ k % c) % c
= (a ^ k % c) ^ 2 % c
如果b為奇數， 不妨設b = 2k + 1，那么
a ^ b % c
= (a * a ^ 2k) % c
= (a % c) * (a ^ 2k % c) % c
= (a % c) * ((a ^ k % c) ^ 2 % c) % c
可見，無論奇偶，計算規模都可以縮至原來的一半，時間復雜度由O(b)降至O(logb)，
根據以上遞推式，很容易寫出解決該問題的遞回演算法，
int powmod(int a, int b, int c) {
if (0 == b) return 1;
long long x = powmod(a, b/2, c);
x = x * x % c;
if (b & 1) x = x * a % c;
return x;
}
如果將實作改成迭代方式就是這樣：
int powmod(int a, int b, int c) {
long long x = 1, t = a;
while (b) {
if (b & 1) x = x * t % c;
t = t * t % c;
b /= 2;
}
return x;
}
資源傳送門
- 關注【做一個柔情的程式猿】公眾號
- 在【做一個柔情的程式猿】公眾號后臺回復 【python資料】【2020秋招】 即可獲取相應的驚喜哦！
「?? 感謝大家」
- 點贊支持下吧，讓更多的人也能看到這篇內容（收藏不點贊，都是耍流氓 -_-）
- 歡迎在留言區與我分享你的想法，也歡迎你在留言區記錄你的思考程序，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/192877.html
標籤：其他
上一篇：艾默生質量流量計的正確安裝