# Fibonacci2

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