快速幂 与 取余运算

#include <bits/stdc++.h>
long long binaryPow(long long a,long long b,long long m){
	if(b == 0)	return 1;
	else if(b%2==1)	return a*binaryPow(a,b-1,m)%m;
	else
	{
		long long num = binaryPow(a, b/2, m) % m;	//优化 
		return num * num % m;
	}
	// 不直接写成return binaryPow(a, b/2, m) * binaryPow(a, b/2, m)
}
int main()
{
	long long b,p,k,c;
	std::scanf("%lld%lld%lld",&b,&p,&k);
	c=b;	b%=k;
	long long ans=binaryPow(b,p,k);
	std::printf("%lld^%lld mod %lld=%lld",c,p,k,ans%k);
	return 0;
}

快速幂 与 取余运算

原文：https://www.cnblogs.com/cyl-oi-miracle/p/13438052.html