参考博客:http://blog.csdn.net/xiaotan1314/article/details/47090773
题目链接:http://lx.lanqiao.cn/problem.page?gpid=T375
问题描述
给定A, B, P,求(A^B) mod P。
输入格式
输入共一行。
第一行有三个数,N, M, P。
第一行有三个数,N, M, P。
输出格式
输出共一行,表示所求。
样例输入
2 5 3
样例输出
2
数据规模和约定
共10组数据
对100%的数据,A, B为long long范围内的非负整数,P为int内的非负整数。
对100%的数据,A, B为long long范围内的非负整数,P为int内的非负整数。

代码:
#include<cstdio> #include<iostream> #include<cmath> #define PI 3.1415926 using namespace std; typedef long long LL; int main() { LL x, m,res; int mod; while(scanf("%I64d%I64d%d", &x, &m, &mod)!=EOF){ res=1; x %= mod; while(m>0){ //log(n)的时间复杂度 if( m & 1) res= res * x % mod; //如果是奇数 则多乘一次本身 x = x * x % mod; //将x平方 m >>= 1; } printf("%d\n", res); } return 0; }