快速幂

计算 \(a^{0b10101010}\) :

\[\begin{aligned} a^{0b10101010} &= a^{0b10000000} + a^{0b100000} + a^{0b1000} + a^{0b10} \\ \\ a^{2^7 + 2^5 + 2^3 + 2^1} &= a^{2^7} \times a^{2^5} \times a^{2^3} \times a^{2^1} \end{aligned} \]

并且我们有：\(a^{2^{i + 1}} = a^{2^{i}} \times a^{2^{i}}\)；

我们只需要定义一个 \(i\) 和 \(mo\):

初始化时 \(i = 1\), \(mo = a\)，\(i\) 代表 \(mo\) 是 \(a\) 的 \(i\) 次方；

如果 \(i\ \&\ n \neq 0\)，\(ans = ans * mo\)

\(i <<= 1, mo = mo * mo\)

typedef __int128_t int128;

// 防止溢出 LL 的乘法
inline LL qmul(int128 a, int128 b, LL p)
{
    return a * b % p;
}

// 快速幂
LL qpow(LL a, LL n, LL p)
{
    LL i = 1, ans = 1, mo = a;
    while (i <= n)
    {
        if (i & n) ans = qmul(ans, mo, p);
        mo = qmul(mo, mo, p);
        i <<= 1;
    }
    return ans;
}