时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
输入b,p,k的值,编程计算bp mod k的值。其中的b,p,k*k为长整型数(2^31范围内)。
输入描述 Input Description
b p k
输出描述 Output Description
输出b^p mod k=?
=左右没有空格
样例输入 Sample Input
2 10 9
样例输出 Sample Output
2^10 mod 9=7
数据范围及提示 Data Size & Hint
1 #include<iostream>
2 using namespace std;
3 int tot;
4 int b,p,k;
5 int f(int p)
6 {
7 if(p==0)return 1;
8 int t=f(p/2)%k;
9 t=(t*t)%k;
10 if(p%2==1)
11 t=(t*b)%k;
12 return t;
13 }
14 int main()
15 {
16
17 cin>>b>>p>>k;
18 int o=b;
19 b%=k;
20 cout<<o<<"^"<<p<<" mod "<<k<<"="<<f(p);
21 return 0;
22 }