• 快速幂
• 慢速乘

快速幂

快速求幂，防止爆炸%p

利用十进制数字 nn 的二进制表示，可对快速幂进行数学化解释 。

• a ^ n % p

long poww(long a, long n, long p) {
    long ans = 1;
    while (n > 0) {
        if ((n & 1) != 0) ans = ans * a % p;//若不取模就去掉p
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

慢速乘

• 对很大的数取模时，这时计算机的long long进行乘法就会爆掉
• 将a 或 b 转化为二进制
• a*b % p

ll mul(ll a, ll b, ll p) {
    ll ans = 0;
    while (b) {
        if (b & 1) ans += a, ans %= p;
        a *= 2, a %= p;
        b >>= 1;
    }
    return ans;
}