『算法-ACM 竞赛』算法竞赛进阶指南-快速幂，求 a^b mod p

// 快速幂，求 a^b mod p
int power(int a, int b, int p) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = (long long)ans _ a % p;
a = (long long)a _ a % p;
}
return ans;
}

// 64 位整数乘法的 O(log b)算法
long long mul(long long a, long long b, long long p) {
long long ans = 0;
for (; b; b >>= 1) {
if (b & 1) ans = (ans + a) % p;
a = a \* 2 % p;
}
return ans;
}

// 64 位整数乘法的 long double 算法
long long mul(long long a, long long b, long long p) {
a %= p, b %= p; // 当 a,b 一定在 0~p 之间时，此行不必要。
long long c = (long double)a _ b / p;
long long ans = a _ b - c \* p;
if (ans < 0) ans += p;
else if (ans >= p) ans -= p;
return ans;
}