Multiply, Power and Inverse
Jump to navigation
Jump to search
Power
LL bin(LL x, LL n, LL MOD) {
LL ret = MOD != 1;
for (x %= MOD; n; n >>= 1, x = x * x % MOD)
if (n & 1) ret = ret * x % MOD;
return ret;
}
To prevent intermediate result exceeds the range of long long:
LL bin(LL x, LL n, LL MOD) {
LL ret = MOD != 1;
for (x %= MOD; n; n >>= 1, x = mul(x, x, MOD))
if (n & 1) ret = mul(ret, x, MOD);
return ret;
}
Multiply
LL mul(LL a, LL b, LL m) {
LL ret = 0;
while (b) {
if (b & 1) {
ret += a;
if (ret >= m) ret -= m;
}
a += a;
if (a >= m) a -= m;
b >>= 1;
}
return ret;
}
[math]\displaystyle{ O(1) }[/math] version:
LL mul(LL u, LL v, LL p) {
return (u * v - LL((long double) u * v / p) * p + p) % p;
}
Inverse
LL inv(LL x, LL MOD) { return pown(x, MOD - 2, MOD); }