fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios::sync_with_stdio(5+2==2006); cin.tie(0); cout.tie(0);
  4. #define ll long long
  5. #define maxn
  6. struct matrix{
  7.     ll a[2][2];
  8. };
  9. ll mod, a, b;
  10. ll mul(ll a, ll b){
  11.     ll res=0;
  12.      a%=mod;
  13.     while (b){
  14.         if (b%2){
  15.             res+=a;
  16.         }
  17.         a*=2;
  18.         a%=mod;
  19.         b/=2;
  20.     }
  21.     return res;
  22. }
  23. matrix mul_matrix(matrix a, matrix b){
  24.     matrix res={0,0,0,0};
  25.     for (int i=0;i<2;i++){
  26.         for (int j=0;j<2;j++){
  27.             for (int k=0;k<2;k++){
  28.                 res.a[i][j]+=mul(a.a[i][k], b.a[k][j]);
  29.                 res.a[i][j]%=mod;
  30.             }
  31.         }
  32.     }
  33.     return res;
  34. }
  35. matrix powmatrix(matrix a, ll b){
  36.     matrix res={1,0,0,1};
  37.     while (b){
  38.         if (b%2){
  39.             res=mul_matrix(res,a);
  40.         }
  41.         a=mul_matrix(a,a);
  42.         b/=2;
  43.     }
  44.     return res;
  45.  
  46. }
  47. int main(){
  48.     faster;
  49.     cin>>a>>b>>mod;
  50.     ll n=__gcd(a,b);
  51.     matrix f={1,1,1,0};
  52.     f=powmatrix(f,n);
  53.     cout<<f.a[1][0];
  54.  
  55.  
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Fmks9M
language:
C++ (gcc 8.3)
created:
2 days 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!