Skip to content

Instantly share code, notes, and snippets.

@ssanin82
Last active August 29, 2015 14:11
Show Gist options
  • Save ssanin82/42a1e3cba5e4adc34d7d to your computer and use it in GitHub Desktop.
Save ssanin82/42a1e3cba5e4adc34d7d to your computer and use it in GitHub Desktop.
C++: Fast power of number modulo x
inline long long fastmodpow(long long a, long long b, long long x) {
if (!x || !a) {
return 0;
}
if (1 == a) {
return 1;
}
a %= x;
if (1 == b) {
return a;
}
long long pow = 1;
long long res = 1;
long long last_pw = a;
long long last_i = 1;
while (b) {
if (b & 1) {
long long pw = last_pw;
long long i = last_i;
while (i < pow) {
pw *= pw;
pw %= x;
i <<= 1;
}
last_pw = pw;
last_i = i;
res *= pw;
res %= x;
}
pow <<= 1;
b >>= 1;
}
return int(res % x);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment