Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int s[3][3];
  4. void mul(int a[3][3],int b[3][3])
  5. {
  6.     for(int i=0;i<3;i++){
  7.         for(int j=0;j<3;j++){
  8.             s[i][j]=0;
  9.             for(int k=0;k<3;k++){
  10.                 s[i][j]+=a[i][k]*b[k][j];
  11.             }
  12.         }
  13.     }
  14.     for(int i=0;i<3;i++){
  15.         for(int j=0;j<3;j++){
  16.             a[i][j]=s[i][j];
  17.         }
  18.     }
  19. }
  20. int pow(int f[3][3],int n)
  21. {
  22.     if(n==1){
  23.         return f[0][0]+f[0][1]*2+f[0][2]*3;
  24.     }
  25.     int m[3][3]={{1,1,1},{1,0,0},{0,1,0}};
  26.  
  27.     pow(f,n/2);
  28.     mul(f,f);
  29.     if(n%2!=0){
  30.         mul(f,m);
  31.     }
  32.     return f[0][0]*1+f[0][1]*2+f[0][2]*3;
  33. }
  34. int fib(int n)
  35. {
  36.     if(n==2){
  37.         return 2;
  38.     }
  39.     if(n==1) return 1;
  40.     if(n==3) return 3;
  41.     int f[3][3]={{1,1,1},{1,0,0},{0,1,0}};
  42.  
  43.     return pow(f,n-3);;
  44. }
  45. int main()
  46. {
  47.     while(1){
  48.         int a,b,n;
  49.         cin>>n;
  50.         cout<<fib(n)<<endl;
  51.     }
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement