题目描述
输入 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^p = b^(p-1) * b^(p-1)
AC 代码:
- #include<iostream>
- #include<iomanip>
- #include<cstdio>
- using namespace std;
- long long b,p,k;
- long long ksm(long long p){
- if(b==0) return 0;
- if(p==0) return 1;
- long long x=ksm(p/2)%k;
- if(p%2==0) return x*x%k;
- else return x*x%k*b%k;
- }
- int main(){
- cin>>b>>p>>k;
- cout<<b<<"^"<<p<<"mod"<<k<<'='<<ksm(p)%k;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2964788.html