content/math/modExp.cpp


1
2
3
4
5
6

ll powMod(ll a, ll b, ll n) {
	if(b == 0) return 1;
	if(b == 1) return a % n;
	if(b & 1) return (powMod(a, b - 1, n) * a) % n;
	else return powMod((a * a) % n, b / 2, n);
}