Binary Exponentiation

binExp32.cpp

int binExp(int b, int pw) {
    if (pw == 0)
        return 1;
    return binExp(b * b % MOD, pw / 2) * (pw & 1 ? b : 1) % MOD;
}

binExp64.cpp

const int bits = 10;
const int po = 1 << bits;
// if all numbers are less than 2ˆk , set bits = 64−k
ull modMul(ull a, ull b, ull &c) {
    ull x = a * (b & (po - 1)) % c;
    while ((b >>= bits) > 0) {
        a = (a << bits) % c;
        x += (a * (b & (po - 1))) % c;
    }
    return x % c;
}
ull binExp(ull b, ull pw, ull MOD) {
    if (pw == 0)
        return 1;
    return modMul(binExp(modMul(b, b, MOD), pw / 2, MOD), (pw & 1 ? b : 1), MOD);
};

BinExp64 runs in O(64/bits * log b)