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