fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. const long long mod = 1e9 + 9;
  5. long long F[2][2], M[2][2];
  6. long long n;
  7.  
  8. void Mul(long long f[2][2], long long m[2][2]) {
  9. 	long long x = (f[0][0]*m[0][0] % mod + f[0][1]*m[1][0] % mod) % mod;
  10. 	long long y = (f[0][0]*m[0][1] % mod + f[0][1]*m[1][1] % mod) % mod;
  11. 	long long z = (f[1][0]*m[0][0] % mod + f[1][1]*m[1][0] % mod) % mod;
  12. 	long long t = (f[1][0]*m[0][1] % mod + f[1][1]*m[1][1] % mod) % mod;
  13. 	f[0][0] = x; f[0][1] = y;
  14. 	f[1][0] = z; f[1][1] = t;
  15. }
  16.  
  17. void Pow(long long f[2][2], long long n) {
  18. 	if (n <= 1) return;
  19. 	Pow(f, n/2);
  20. 	Mul(f, f);
  21. 	if (n % 2 == 1) Mul(f, M);
  22. }
  23.  
  24. void solve() {
  25. 	F[0][0] = F[0][1]= F[1][0] = 1;
  26. 	F[1][1] = 0;
  27. 	M[0][0] = M[0][1]= M[1][0] = 1;
  28. 	M[1][1] = 0;
  29. 	scanf("%lld", &n);
  30. 	if (n <= 0) printf("0");
  31. 	else {
  32. 		Pow(F, n + 1);
  33. 		printf("%lld", F[0][0] - 1);
  34. 	}
  35. }
  36. int main() {
  37. 	solve();
  38. }
Success #stdin #stdout 0s 5448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GKwBFI
language:
C (gcc 8.3)
created:
2 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!