[cpp]  view plain  copy
  1. int quick(int a,int b,int c)  

时间复杂度为O(log(2)n);

可以将b转化为二进制

b为偶数时 a = a * a % c;

b为奇数时 ans = ans * a % c;

[cpp]  view plain  copy
  1. #include <stdio.h>  
  2. #include <iostream>  
  3. using namespace std;  
  4. int quick(int a,int b,int c)  
  5. {  
  6.     int ans=1;   //记录结果  
  7.     a=a%c;   //预处理，使得a处于c的数据范围之下 2  
  8.     while(b!=0)//100  
  9.     {  
  10.         //if(b&1)  
  11.         if(b % 2 == 1) ans=(ans*a)%c;   
  12.         cout <<"b1 = " << b;  
  13.           //如果b的二进制位不是0，那么我们的结果是要参与运算的  
  14.     b /= 2;    //b >>= 1;  
  15.         cout << "b = " << b;//二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位  
  16.         a=(a*a)%c;   //不断的加倍 0  
  17.     }  
  18.     return ans;  
  19. }  
  20. int main()  
  21. {  
  22.     int a , b , c;  
  23.     cin >> a >> b >> c;  
  24.     cout << quick(a , b , c) << endl;  
  25.     return 0;  
[cpp]  view plain  copy
  1. #include <stdio.h>  
  2. #include <iostream>  
  3. using namespace std;  
  4. int main()  
  5. {  
  6.     long long int a , b , c;  
  7.     int t;  
  8.     scanf("%d" , &t);  
  9.     while(t--)  
  10.     {  
  11.       
  12.         cin >> a >> b >> c;  
  13.         long long int ans = 1;  
  14.           
  15.         while(b>1)  
  16.         {  
  17.             cout << b << endl;  
  18.             if(b % 2 == 1)  
  19.             {  
  20.                 ans *= ans * a % c;  
  21.                 b--;    //  一定要加上b--,否则为奇数时，会死循环                                                                                                                                                                                                 
  22.             }  
  23.             else  
  24.             {  
  25.                 b /= 2;  
  26.               
  27.             }  
  28.                 a = a * a % c;  
  29.         }  
  30.     cout << ans << endl;  
  31.     }  
  32.       
  33.     return 0;  
  34. }  

}
举报
收藏
赞