P1226 取余运算||快速幂

admin

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

WJL

1. #include<iostream>
   
2. using namespace std;
   
3. long long  b,p,k;
   
4. long long aa,bb,cc;
   
5. long long ans;
   
6. int main()
   
7. {
   
8.     cin>>b>>p>>k;
   
9.     aa=b;
   
10.     bb=p;
    
11.     long long ans=1;
    
12. while(bb>0)
    
13. {
    
14.     if(bb%2==1)
    
15.         ans=ans%k*aa%k;
    
16.     aa=aa%k*aa%k;
    
17.     bb/=2;
    
18. }
    
19. ans=ans%k;
    
20. cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans;
    
21.    return 0;
    
22. }
    

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. long long int b,aa,p,k;
   
4. int i,j;
   
5. long long int ksm(long long int a,long long int c,long long int d)
   
6. {
   
7.     int t=1;aa=a;
   
8.     while(c>0)
   
9.     {
   
10.         if(c%2!=0)t=t*aa%k;
    
11.         aa=aa*aa%k;c=c/2;
    
12.     }
    
13.     return t%k;
    
14. }
    
15. int main()
    
16. {
    
17.     cin>>b>>p>>k;
    
18.     cout<<b<<"^"<<p<<" mod "<<k<<"="<<ksm(b,p,k);
    
19.     return 0;
    
20. }
    

复制代码