NOJ - T012
[編輯] [转简体] (简体译文)
|
作者:huidong
| 分類:【編程】NOJ 和 C 程序設計習題
[
14 瀏覽
0 評論
4 贊
4 踩
]
概要
快速冪算法
正文
#include <stdio.h> #include <math.h> int main() { // 由於輸入爲正整數,且最大取到 2^63 故用 llu // ans 存儲最終結果 unsigned long long a, b, m, ans = 1; scanf("%llu %llu %llu", &a, &b, &m); while (b) { if (b & 1) ans = (ans * a) % m; // 根據 b 的當前位是否爲 1 確定 ans 這一循環是否需要乘入 a, // 乘完之後立即取模,答案不變 a = (a * a) % m; // 每次循環 a 變成 (a^2) % m,這是最快也是最省空間的辦法 b >>= 1; // 按位閱讀 b } printf("%llu", ans); return 0; }
代碼筆記