fork download
copy 
  1. /*=====================================
  2. *   
  3. *   AUTHOR : maxkibble
  4. *   CREATED: 2019.09.08 15:39:59
  5. *   PROBELM: UVALive 3722
  6. *
  7. =====================================*/
  8.  
  9.  
  10. #include <bits/stdc++.h>
  11.  
  12. using namespace std;
  13.  
  14. #define fi first
  15. #define se second
  16. #define pb push_back
  17.  
  18. typedef long long ll;
  19. typedef pair<int, int> pii;
  20.  
  21. ll mypow(ll a, ll n, ll c) {
  22.   ll ans = 1;
  23.   while (n) {
  24.     if (n & 1) ans = ans * a % c;
  25.     a = a * a % c;
  26.     n >>= 1;
  27.   }
  28.   return ans;
  29. }
  30.  
  31. int main() {
  32.   ios::sync_with_stdio(false);
  33.   cin.tie(0); cout.tie(0);
  34.   ll x, a, n, c;
  35.   while (cin >> x >> a >> n >> c) {
  36.     if (x == 0) break;
  37.     ll an = mypow(a, n, c);
  38.     ll A = an * x % c;
  39.     ll B = ((an - 1) % c + c) % c * a % c;
  40.     ll C = mypow(a - 1, c - 2, c);
  41.     ll ans;
  42.     if ((a - 1) % c == 0) {
  43.       assert(A == x % c);
  44.       ans = A - n % c;
  45.     }
  46.     else ans = A - B * C;
  47.     ans = (ans % c + c) % c;
  48.     cout << ans << "\n";
  49.   }
  50.   return 0;
  51. }
  52.  
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vgoLxz
language:
C++14 (gcc 8.3)
created:
4 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!