Advertisement
MaxObznyi

Binary pow

May 21st, 2022
635
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #define int long long
  3. using namespace std;
  4.  
  5. /*int pow(int a, int b, int M) {
  6.     if (b == 0) {
  7.         return 1 % M;
  8.     }
  9.     if (b % 2 == 1) {
  10.         return pow(a, b - 1, M) * a % M;
  11.     } else {
  12.         int ak = pow(a, b / 2, M);
  13.         return ak * ak % M;
  14.     }
  15. }*/
  16.  
  17. int pow(int a, int b, int M) {
  18.     int res = 1 % M;
  19.     while (b != 0)
  20.         if (b % 2 == 1) {
  21.             res *= a;
  22.             res %= M;
  23.             b--;
  24.         }
  25.         else {
  26.             a *= a;
  27.             a %= M;
  28.             b /= 2;
  29.         }
  30.     return res;
  31. }
  32.  
  33. signed main()
  34. {
  35.     int t;
  36.     cin >> t;
  37.     while (t--) {
  38.         int a, b, M;
  39.         cin >> a >> b >> M;
  40.         cout << pow(a, b, M) << "\n";
  41.     }
  42.     return 0;
  43. }
  44.  
Advertisement
RAW Paste Data Copied
Advertisement