题解 | #快速幂#
快速幂
https://www.nowcoder.com/practice/defdedf4fe984c6c91eefa6b00d5f4f0?tpId=308&tqId=2403107&ru=/exam/oj&qru=/ta/algorithm-start/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D308
#include <iostream>
int main(int argc, char *argv[]) {
long long count, a, b, q;
std::cin >> count;
while (--count >= 0) {
std::cin >> a >> b >> q;
long long res = 1;
while (b) {
if (b & 1) {
// res存放的全是奇数个的乘积，最后移位一定是1，这样将前面累积的偶数幂乘上去
res = (res * a) % q;
}
// 每次移动移位，减少一个平方幂
a = (a * a) % q;
b >>= 1;
}
std::cout << res << std::endl;
}
return 0;
}
