Created 02/02/2020 at 02:52PM

快速幂

int qpow(int a, int b) {
    int ans = 1, base = a;
    while (b != 0) {
        if (b & 1) ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

大数相乘取模

借鉴快速幂的思想

long long qmul(long long a, long long b, long long mod) {
    long long res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        (a <<= 1) %= mod;
        b >>= 1;
    }
    return res;
}

快速大数幂

long long qpow_mod(long long a, long long n, long long mod) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}