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. OK, I Understand
Top