SHARE
TWEET

Fibonacci2

a53 Jan 24th, 2020 (edited) 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #define M 666013;
  3. using namespace std;
  4. struct Mat /// Struct ce retine o matrice 2x2
  5. {
  6.     int mat[2][2];
  7. };
  8. const Mat nullMat= /// Elementul neutru la inmultirea matricelor 2x2
  9. {
  10.     {{1, 0},
  11.      {0, 1}}
  12. };
  13. const Mat initMat= /// Matricea pe care o ridicam la puterea k
  14. {
  15.     {{1, 1},
  16.      {1, 0}}
  17. };
  18.  
  19. Mat prod(Mat a,Mat b) /// Functie ce calculeaza a*b
  20. {
  21.     Mat ret;
  22.     ret.mat[0][0]=(1LL*a.mat[0][0]*b.mat[0][0]+1LL*a.mat[0][1]*b.mat[1][0])%M;
  23.     ret.mat[0][1]=(1LL*a.mat[0][0]*b.mat[0][1]+1LL*a.mat[0][1]*b.mat[1][1])%M;
  24.     ret.mat[1][0]=(1LL*a.mat[1][0]*b.mat[0][0]+1LL*a.mat[1][1]*b.mat[1][0])%M;
  25.     ret.mat[1][1]=(1LL*a.mat[1][0]*b.mat[0][1]+1LL*a.mat[1][1]*b.mat[1][1])%M;
  26.     return ret;
  27. }
  28.  
  29. Mat pwr(Mat mat,int n) /// Functie recursiva pentru calcularea mat^n
  30. {
  31.     if(!n)
  32.         return nullMat;
  33.     if(n&1)
  34.         return prod(mat,pwr(prod(mat,mat),n>>1));
  35.     return pwr(prod(mat,mat),n>>1);
  36. }
  37.  
  38. int main()
  39. {
  40.     int n;
  41.     cin>>n;
  42.     cout<<pwr(initMat,n).mat[0][1]<<'\n';
  43.     return 0;
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top