P1226 【模板】快速幂||取余运算 AC于2018.8.22 https://www.luogu.org/problemnew/show/P1226
程序员文章站
2022-05-14 17:17:45
...
题目描述
输入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
【知识补充】
https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E5%B9%82/5500243
【代码】
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
long long int b,p,k,ans=1;
int main()
{
scanf("%lld%lld%lld",&b,&p,&k);
printf("%lld^%lld mod %lld=",b,p,k);
if(p==0)
{
printf("0");
return 0;
}
while(p>0)
{
if(p%2!=0)
ans=ans*b%k;
b=b*b%k;
p=p>>1;
}
printf("%lld",ans);
return 0;
}
上一篇: Java基础知识小结