跳转至

快速幂

在 \(O(\log n)\) 的时间复杂度计算 \(b^a\)。

1
2
3
4
5
6
7
ull res = 1;
while(b) {
    if(b & 1) (res *= a) %= p;
    (a *= a) %= p;
    b >>= 1;
}
printf("%lld", res % p);