fork(3) download
copy 
  1. //FIBOSQRT
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define ll     unsigned int
  8. long long MOD;
  9.  
  10. void multiply(ll a[3][3],ll b[3][3])
  11. {
  12.  
  13.     long long p,q,r,s,t,u,v,w,x;
  14.  
  15.     p=(long long)a[0][0]*b[0][0]+(long long)a[0][1]*b[1][0]+(long long)a[0][2]*b[2][0];
  16.     q=(long long)a[1][0]*b[0][0]+(long long)a[1][1]*b[1][0]+(long long)a[1][2]*b[2][0];
  17.     r=(long long)a[2][0]*b[0][0]+(long long)a[2][1]*b[1][0]+(long long)a[2][2]*b[2][0];
  18.  
  19.     s=(long long)a[0][0]*b[0][1]+(long long)a[0][1]*b[1][1]+(long long)a[0][2]*b[2][1];
  20.     t=(long long)a[1][0]*b[0][1]+(long long)a[1][1]*b[1][1]+(long long)a[1][2]*b[2][1];
  21.     u=(long long)a[2][0]*b[0][1]+(long long)a[2][1]*b[1][1]+(long long)a[2][2]*b[2][1];
  22.  
  23.     v=(long long)a[0][0]*b[0][2]+(long long)a[0][1]*b[1][2]+(long long)a[0][2]*b[2][2];
  24.     w=(long long)a[1][0]*b[0][2]+(long long)a[1][1]*b[1][2]+(long long)a[1][2]*b[2][2];
  25.     x=(long long)a[2][0]*b[0][2]+(long long)a[2][1]*b[1][2]+(long long)a[2][2]*b[2][2];
  26.  
  27.     //matrix res(3,vector<ll>(3));
  28.  
  29.     a[0][0]=(ll)(p%MOD);
  30.     a[1][0]=(ll)(q%MOD);
  31.     a[2][0]=(ll)(r%MOD);
  32.     a[0][1]=(ll)(s%MOD);
  33.     a[1][1]=(ll)(t%MOD);
  34.     a[2][1]=(ll)(u%MOD);
  35.     a[0][2]=(ll)(v%MOD);
  36.     a[1][2]=(ll)(w%MOD);
  37.     a[2][2]=(ll)(x%MOD);
  38.  
  39.     //return res;
  40.  
  41. }
  42.  
  43. void power(ll a[3][3],ll b[3][3],long long n)
  44. {
  45.  
  46.     if(n<=1)
  47.     return ;
  48.  
  49.     else if(n&1)
  50.          { 
  51.  
  52.              power(a,b,n-1);
  53.              multiply(a,b);
  54.  
  55.          }    
  56.  
  57.          else {
  58.  
  59.                   power(a,b,n>>1);
  60.  
  61.                   multiply(a,a);
  62.  
  63.               }
  64.  
  65. }
  66.  
  67. int main()
  68. {
  69.  
  70.     int t;
  71.     long long n;
  72.     ll a,b;
  73.  
  74.     scanf("%d",&t);
  75.  
  76.     while(t--)
  77.     {
  78.  
  79.         scanf("%u%u%u%lld",&a,&b,&MOD,&n);
  80.  
  81.         ll f[3],temp[3][3];
  82.  
  83.         f[0]=(ll)sqrt(3+(long long)a*b);//G(0)
  84.         f[1]=b;//f(1)
  85.         f[2]=a;//f(0)
  86.  
  87.         ll t[3][3];
  88.  
  89.         t[0][0]=temp[0][0]=1;
  90.         t[0][1]=temp[0][1]=1;
  91.         t[0][2]=temp[0][2]=0;
  92.         t[1][0]=temp[1][0]=2;
  93.         t[1][1]=temp[1][1]=1;
  94.         t[1][2]=temp[1][2]=1;
  95.         t[2][0]=temp[2][0]=0;
  96.         t[2][1]=temp[2][1]=1;
  97.         t[2][2]=temp[2][2]=0;
  98.  
  99.         //cout<<"Executing..."<<endl;
  100.  
  101.  
  102.         power(t,temp,n-1);
  103.  
  104.         //cout<<"Executing..."<<endl;
  105.  
  106.         ll ans=(ll)(((long long)t[1][0]*f[0]+(long long)t[1][1]*f[1]+(long long)t[1][2]*f[2])%MOD);
  107.  
  108.         printf("%u\n",(ll)ans);
  109.  
  110.     }
  111.  
  112.     return 0;
  113.  
  114. }
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
Success #stdin #stdout 0s 2732KB
comments (?)
stdin
copy 
2
1 1 10 5
2 3 100 6
stdout
copy 
4
82
https://ideone.com/4ho8nX
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

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!