fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. // #define mod 1000000007
  5. ll mod, m;
  6. struct matran
  7. {
  8.         ll a[2][2];
  9.         void print()
  10.         {
  11.                 for (ll i = 0; i < 2; i++)
  12.                 {
  13.                         for (ll j = 0; j < 2; j++)
  14.                                 cout << a[i][j] << " ";
  15.                         cout << '\n';
  16.                 }
  17.         }
  18. };
  19. matran mot;
  20. struct cap
  21. {
  22.         ll u, u_plus_1;
  23.         void print()
  24.         {
  25.                 cout << u << " " << u_plus_1 << '\n';
  26.         }
  27. };
  28. ll f(ll a, ll n, ll mod)
  29. {
  30.         ll res = a, ans = 0;
  31.         while (n)
  32.         {
  33.                 if (n % 2)
  34.                         ans = (ans + res) % mod;
  35.                 res = (res + res) % mod;
  36.                 n /= 2;
  37.         }
  38.         return ans;
  39. }
  40. ll po(ll a, ll n)
  41. {
  42.         ll res = a, ans = 1;
  43.         while (n)
  44.         {
  45.                 if (n % 2)
  46.                         ans = f(ans, res, mod);
  47.                 res = f(res, res, mod);
  48.                 n /= 2;
  49.         }
  50.         return ans;
  51. }
  52. ll aka(ll p, ll alpha)
  53. {
  54.         if (alpha == 0)
  55.                 return 1;
  56.         if (alpha == 1)
  57.                 return (p + 1) % mod;
  58.         if (alpha % 2 == 1)
  59.                 return (f(p, aka(p, alpha - 1), mod) + 1) % mod;
  60.         if (alpha % 2 == 0)
  61.                 return (f((po(p, alpha / 2) + 1), ((aka(p, alpha / 2) - 1 + mod) % mod), mod) + 1) % mod;
  62. }
  63. cap prod1(cap pp, matran X)
  64. {
  65.         cap ans;
  66.         ans.u = (f(pp.u, X.a[0][0], mod) + f(pp.u_plus_1, X.a[1][0], mod)) % mod;
  67.         ans.u_plus_1 = (f(pp.u, X.a[1][0], mod) + f(pp.u_plus_1, X.a[1][1], mod)) % mod;
  68.         return ans;
  69. }
  70. matran prod(matran A, matran B)
  71. {
  72.         matran anss;
  73.         anss.a[0][0] = (f(A.a[0][0], B.a[0][0], mod) + f(A.a[0][1], B.a[1][0], mod)) % mod;
  74.         anss.a[0][1] = (f(A.a[0][0], B.a[0][1], mod) + f(A.a[0][1], B.a[1][1], mod)) % mod;
  75.         anss.a[1][0] = (f(A.a[1][0], B.a[0][0], mod) + f(A.a[1][1], B.a[1][0], mod)) % mod;
  76.         anss.a[1][1] = (f(A.a[1][0], B.a[0][1], mod) + f(A.a[1][1], B.a[1][1], mod)) % mod;
  77.         return anss;
  78. }
  79. matran po(matran X, ll n)
  80. {
  81.         matran res = X, ans = mot;
  82.         while (n)
  83.         {
  84.                 if (n % 2)
  85.                         ans = prod(ans, res);
  86.                 res = prod(res, res);
  87.                 n /= 2;
  88.         }
  89.         return ans;
  90. }
  91. int main()
  92. {
  93.         ll x, n, m;
  94.         cin >> x >> n >> m;
  95.         cap init;
  96.         init.u = 1;
  97.         init.u_plus_1 = 1;
  98.         matran M;
  99.         M.a[0][0] = x;
  100.         M.a[0][1] = 0;
  101.         M.a[1][0] = 1;
  102.         M.a[1][1] = 1;
  103.         mot.a[0][0] = 1;
  104.         mot.a[0][1] = 0;
  105.         mot.a[1][0] = 0;
  106.         mot.a[1][1] = 1;
  107.         mod = m;
  108.         matran res = po(M, n);
  109.         cap ansss = prod1(init, res);
  110.  
  111.         cout << ansss.u << '\n';
  112. }
Success #stdin #stdout 0s 4964KB
comments (?)
stdin
copy 
2 6 1000
stdout
copy 
127
https://ideone.com/WuM87A
language:
C++ (gcc 8.3)
created:
3 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!