fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> pow_mod_seq(int a, int m, int &o, int &p)
  8. {
  9.     vector<int> s = {1};
  10.     for (;;) {
  11.         int t = s.back() * a % m;
  12.         auto i = find(s.begin(), s.end(), t);
  13.         if (i == s.end()) {
  14.             s.push_back(t);
  15.         } else {
  16.             o = (i - s.begin());
  17.             p = s.size() - o;
  18.             break;
  19.         }
  20.     }
  21.     return s;
  22. }
  23.  
  24. int powmod(int a, int n, int m)
  25. {
  26.     if (n == 0) {
  27.         return 1;
  28.     } else if (n & 1) {
  29.         return a * powmod(1LL * a * a % m, n / 2, m) % m;
  30.     } else {
  31.         return powmod(1LL * a * a % m, n / 2, m) % m;
  32.     }
  33. } 
  34.  
  35. int powpowmod100(int n)
  36. {
  37.     if (n == 2) {
  38.         return 16;
  39.     }
  40.     int m = n % 100;
  41.     if (m <= 1) {
  42.         return m;
  43.     }
  44.     int offset, period;
  45.     auto s = pow_mod_seq(m, 100, offset, period);
  46.  
  47.     int i = powmod(n, n, period) - offset;
  48.     while (i < 0) {
  49.         i += period;
  50.     }
  51.     return s[offset + i];
  52. }
  53.  
  54. int main()
  55. {
  56.     for (int n; cin >> n; ) {
  57.         cout << n << " => " << powpowmod100(n) << endl;
  58.     }
  59. }
  60.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
1
2
3
4
11
13
100
777
stdout 
1 => 1
2 => 16
3 => 87
4 => 96
11 => 11
13 => 53
100 => 0
777 => 97
https://ideone.com/HUZiK8
language:
C++14 (gcc 8.3)
created:
5 years 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!