递归

$时间复杂度: O(log_{2} k)$

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull modPow(ull a,ull b,ull p){
	if(b==0)return 1;
	a=a%p;
	if(b%2==1)return a*modPow(a*a%p,b/2,p)%p;
	else return modPow(a*a%p,b/2,p)%p;}
int main() {
	ull a,b,p;
	cin>>a>>b>>p;
	cout<<a<<"^"<<b<<" mod "<<p<<"="<<modPow(a,b,p);
	return 0; }