a53

Fibonacci2

a53
Jan 24th, 2020
130
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