信息学奥赛一本通T1326-取余运算

解题思路:分治思想 （a*b）% k = （（a%k）*（b%k）) % k

注意事项:数据类型，确保乘积运算在int范围

参考代码:

#include<iostream>
#include<limits>
#include<cstring>
#include<cmath>
using namespace std;
long long ob,p;
int b,k,res;
int dfs(long long n){
	if(n == 0) return 1;
	int res = dfs(n/2) % k;
	res = (res * res) % k;
	if(n % 2 == 1) res = ((res % k) * (b % k))%k;	
	return res;	
}
int main()
{
	cin >> ob >> p >> k;
	b = ob % k; 
	res = dfs(p);
	printf("%lld^%lld mod %d=%d",ob,p,k,res);	
	return 0;
}