P1226 【模板】快速幂||取余运算
程序员文章站
2022-03-03 09:01:05
...
题目描述
输入b,p,k的值,求b^p mod k的值。其中b,p,k为长整型数。
输入输出格式
输入格式:
三个整数b,p,k.
输出格式:
输出“b^p mod k=s”
s为运算结果
输入输出样例
输入样例#1: 复制
2 10 9
输出样例#1: 复制
2^10 mod 9=7
思路:
快速幂模板题,注意使用long long不然会有几个点卡住
代码:
#include<iostream>
#define ll long long
using namespace std;
ll b,p,k;
ll quickPower(ll a,ll b,ll m)
{
ll ans=1,base=a;
while(b > 0)
{
if(b & 1)//与 b mod 2 == 1等效,也就是奇数
{
ans *= base;
ans %= m;
}
base *= base;
base %= m;
b >>= 1; //与 b/=2 等效
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"="<<quickPower(b,p,k)%k<<endl;
return 0;
}
上一篇: Python笔记: 执行run.py文件
下一篇: 静态工厂方法模式