• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Fibonacci2_of

a guest Jan 24th, 2020 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2.
3. using namespace std;
4.
5. typedef int MatFib[2][2];
6.
7. const int MOD = 666013;
8.
9. void Produs(MatFib A , MatFib B, MatFib P)
10. {
11.     P[0][0] = (1LL * A[0][0] * B[0][0] + 1LL * A[0][1] * B[1][0]) % MOD;
12.     P[0][1] = (1LL * A[0][0] * B[0][1] + 1LL * A[0][1] * B[1][1]) % MOD;
13.     P[1][0] = (1LL * A[1][0] * B[0][0] + 1LL * A[1][1] * B[1][0]) % MOD;
14.     P[1][1] = (1LL * A[1][0] * B[0][1] + 1LL * A[1][1] * B[1][1]) % MOD;
15. }
16.
17. void Atrib(MatFib D ,MatFib S)
18. {
19.     D[0][0] = S[0][0];
20.     D[0][1] = S[0][1];
21.     D[1][0] = S[1][0];
22.     D[1][1] = S[1][1];
23. }
24.
25. int Fibo(int n)
26. {
27.     MatFib A = {{1,1},{1,0}}, B , R = {{1,0},{0,1}};
28.     while(n > 0)
29.     {
30.         if(n % 2 == 1)
31.         {
32.             Produs(R , A, B);
33.             Atrib(R, B);
34.         }
35.         Produs(A, A, B);
36.         Atrib(A , B);
37.         n /= 2;
38.     }
39.
40.     return R[0][1];
41. }
42.
43. int main()
44. {
45.     int n;
46.     cin >> n;
47.     cout << Fibo(n);
48.     return 0;
49. }
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.
Top