fork download
  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. ll sum(ll a, ll n, ll c) {
  32. if (n == 1) {
  33. return a % c;
  34. }
  35. ll k = mypow(a, n >> 1, c);
  36. ll s = sum(a, n >> 1, c);
  37. ll ret = (s + k * s % c) % c;
  38. if (n & 1) ret = (ret + mypow(a, n, c)) % c;
  39. return ret;
  40. }
  41.  
  42. int main() {
  43. ios::sync_with_stdio(false);
  44. cin.tie(0); cout.tie(0);
  45. ll x, a, n, c;
  46. while (cin >> x >> a >> n >> c) {
  47. if (x == 0) break;
  48. ll an = mypow(a, n, c);
  49. ll ans = an * x % c - sum(a, n, c);
  50. ans = (ans % c + c) % c;
  51. cout << ans << "\n";
  52. }
  53. return 0;
  54. }
  55.  
Success #stdin #stdout 0s 4524KB
stdin
Standard input is empty
stdout
Standard output is empty