https://www.luogu.org/problemnew/show/P1226
题目描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。
输入输出格式
输入格式：
三个整数b,p,k.
输出格式：
输出“b^p mod k=s”
s为运算结果
输入输出样例
输入样例#1： 复制
2 10 9
输出样例#1： 复制
2^10 mod 9=7
坑点在于给出的b可能比较大，b*b直接溢出，所以在算之前要先对k取模。
#include<stdio.h>
int main()
{
long long b,p,k,s,a,d;
scanf("%lld%lld%lld",&b,&p,&k);
a=b%k;d=p;s=a;
while(d>0)
{
if(d%2&&d!=1)
{
s*=a;
s=s%k;
}
if(d/2)
{
s*=a;
a=(a*a)%k;
s=s%k;
}
d/=2;
}
printf("%lld^%lld mod %lld=%lld
",b,p,k,s);
return 0;
}