modular exponentiation vs binary exponentiation code example
Example 1: binary exponentiation
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull po(ull n,ull k){
ull x=1;
while(k){
if(k&1)
x*=n;
n*=n;
k>>=1;
}
return x;
}
int main(){
ull n,m;
cin>>n>>m;
cout<<po(n,m);
return 0;
}
Example 2: binary exponentiation modulo m
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}