fork download 
  1. #include <bits/stdc++.h>
  2. #include<math.h>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. typedef long long int ll;
  7.  
  8. ll M = 1000000007;
  9.  
  10. map<ll, ll> mp;
  11.  
  12. long long fibonacci(long long n) {
  13. 	if (mp.count(n))
  14. 	{
  15. 		printf("return for n=%lld f[n]=%lld\n",n,mp[n]);
  16. 		return mp[n];
  17.  
  18. 	}long long k=n/2;
  19. 	printf("k=%lld\n",k);
  20. 	if (n%2==0) { 
  21. 		printf("calling k=%lld  k+1=%lld  and f[n]=%lld n=%lld",k,(k+1),mp[n],n);
  22. 		return mp[n] = fibonacci(k)*(fibonacci(k+1)+fibonacci(k-1)) % M;
  23. 	} else { 
  24. 			printf("odd calling k=%lld  k+1=%lld  and f[n]=%lld n=%lld\n",k,(k+1),mp[n],n);
  25. 		return mp[n] = (fibonacci(k+1)*fibonacci(k+1) + fibonacci(k)*fibonacci(k)) % M;
  26. 	}
  27. }
  28.  
  29.  
  30.  
  31.  
  32. int main()
  33. {
  34.     mp[0]=mp[1]=1;
  35.     ll t;
  36.     scanf("%lld",&t);
  37.     while(t--)
  38.     {
  39.         long long n;
  40.         scanf("%lld",&n);
  41.         printf("%lld\n",fibonacci(n));
  42.     }
  43.     return 0;
  44. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin 
1
3
stdout 
k=1
odd calling k=1  k+1=2  and f[n]=0 n=3
k=1
calling k=1  k+1=2  and f[n]=0 n=2return for n=1 f[n]=1
return for n=2 f[n]=0
return for n=0 f[n]=1
return for n=2 f[n]=1
return for n=1 f[n]=1
return for n=1 f[n]=1
2
https://ideone.com/rTjjw6
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!