fork(11) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define mod 1000000007
  5.  
  6. long long result[2][2]={{1,1},{1,0}};
  7. long long transformation[2][2]={{1,1},{1,0}};
  8. void matrixMul(long long a[2][2],long long b[2][2])
  9. {
  10. 	 int i,j,k;
  11. 	 long long re[2][2] ={0};
  12. 	 for(i=0;i<2;i++) {
  13. 	 	for(j=0;j<2;j++) {
  14. 	 		for(k=0;k<2;k++) {
  15. 	 			re[i][j] = (re[i][j] + (a[i][k]*b[k][j])%mod ) % mod;
  16. 	 		}
  17. 	 	}
  18. 	 }
  19. 	 for(i=0;i<2;i++)
  20. 	 {
  21. 	 	for(j=0;j<2;j++)
  22. 	 	result[i][j]=re[i][j];
  23. 	 }
  24. }
  25.  
  26. void initialize() {
  27. 	result[0][0]=result[0][1]=result[1][0]=1;
  28. 	result[1][1]=0;
  29. }
  30. void power(int n)
  31. {
  32. 	if(n==1)
  33. 	return ;
  34. 	power(n/2);
  35. 	matrixMul(result,result);
  36. 	if(n&1)
  37. 	{
  38. 		matrixMul(result,transformation);
  39. 	}
  40. }
  41.  
  42. int main()
  43. {
  44. 	initialize();
  45. 	int n;
  46. 	cin>>n;
  47.  
  48. 	if(n == 0 || n == 1) {
  49. 		printf("Nth fibonacci = %d\n", n);	
  50. 	}
  51. 	else {
  52. 		power(n-1);
  53. 		printf("Nth fibonacci = %lld\n", result[0][0]);
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 4304KB
comments (?)
stdin
copy 
7
stdout
copy 
Nth fibonacci = 13
https://ideone.com/Sg0s1k
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!