fork download
copy 
  1. /* https://c...content-available-to-author-only...s.com/algebra/binary-exp.html */
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. /// binary exponentiation
  7. long long bigPow(int b, int e)
  8. {
  9.   if (e == 0) return 1;
  10.   long long ret = bigPow(b, e / 2); /// 2 ^ 2 // b = 2 e = 5
  11.   ret = ret * ret;
  12.   if (e & 1) ret = ret * b; /// 2 ^ 5 = 2 ^ 2 * 2 ^ 2 * (2)
  13.   return ret;
  14. }
  15. /// O (log e)
  16.  
  17. long long bigPowMod(int b, int e, int mod)
  18. {
  19.   if (e == 0) return 1;
  20.   long long ret = bigPowMod(b, e / 2, mod); /// 2 ^ 2 // b = 2 e = 5
  21.   ret = ((ret % mod) * (ret % mod)) % mod;
  22.   if (e & 1) ret = (ret * b) % mod; /// 2 ^ 5 = 2 ^ 2 * 2 ^ 2 * (2)
  23.   return ret % mod;
  24. }
  25.  
  26. const int MOD = 1e9 + 7;
  27.  
  28. int main()
  29. {
  30.   ios_base::sync_with_stdio(false), cin.tie(nullptr);
  31.  
  32.   int t;
  33.   cin >> t;
  34.   while (t--) {
  35.     int a, b;
  36.     cin >> a >> b;
  37. //    if (a == 0 and b == 0) {
  38. //      cout << 1 << '\n';
  39. //      continue;
  40. //    }
  41.     cout << bigPowMod(a, b, MOD) << '\n';
  42.   }
  43.  
  44.   return 0;
  45. }
  46.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4eO7y3
language:
C++14 (clang 8.0)
created:
30 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!