modular exponentiation vs binary exponentiation code example

Example 1: binary exponentiation

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
//complexity O(log k)
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;
    //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;
}

Tags:

Cpp Example