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