Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int s[3][3];
- void mul(int a[3][3],int b[3][3])
- {
- for(int i=0;i<3;i++){
- for(int j=0;j<3;j++){
- s[i][j]=0;
- for(int k=0;k<3;k++){
- s[i][j]+=a[i][k]*b[k][j];
- }
- }
- }
- for(int i=0;i<3;i++){
- for(int j=0;j<3;j++){
- a[i][j]=s[i][j];
- }
- }
- }
- int pow(int f[3][3],int n)
- {
- if(n==1){
- return f[0][0]+f[0][1]*2+f[0][2]*3;
- }
- int m[3][3]={{1,1,1},{1,0,0},{0,1,0}};
- pow(f,n/2);
- mul(f,f);
- if(n%2!=0){
- mul(f,m);
- }
- return f[0][0]*1+f[0][1]*2+f[0][2]*3;
- }
- int fib(int n)
- {
- if(n==2){
- return 2;
- }
- if(n==1) return 1;
- if(n==3) return 3;
- int f[3][3]={{1,1,1},{1,0,0},{0,1,0}};
- return pow(f,n-3);;
- }
- int main()
- {
- while(1){
- int a,b,n;
- cin>>n;
- cout<<fib(n)<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement