fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long MOD = 100000000;
  4. struct Mat
  5. {
  6. 	long long x[4][4];
  7. 	Mat()
  8. 	{
  9. 		memset(x, 0 ,sizeof(x));
  10. 	}
  11. 	void I()
  12. 	{
  13. 		memset(x, 0, sizeof(x));
  14. 		x[1][1] = x[2][2] = x[3][3] = 1;
  15. 	}
  16. 	Mat pow(long long y)
  17. 	{
  18. 		Mat re; re.I();
  19. 		Mat tmp = (*this);
  20. 		while(y)
  21. 		{
  22. 			if(y&1) re = re*tmp;
  23. 			tmp = tmp*tmp;
  24. 			y>>=1;
  25. 		}
  26. 		return re;
  27. 	}
  28. 	Mat operator * (const Mat& a)
  29. 	{
  30. 		Mat re;
  31. 		for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) for(int k=1;k<=3;k++)
  32. 		{
  33. 			re.x[i][k] += x[i][j] * a.x[j][k];
  34. 			re.x[i][k] %= MOD;
  35. 		}
  36. 		return re;
  37. 	}
  38. };
  39. Mat trans,ans;
  40. long long out;
  41.  
  42. int main()
  43. {
  44. 	trans.x[2][1] = 1;
  45. 	trans.x[3][2] = 1;
  46. 	trans.x[1][3] = trans.x[2][3] = trans.x[3][3] = 1;
  47.  
  48. 	//f(1234567890*1234567890)
  49. 	ans = trans.pow(1234567890LL*1234567890LL - 1);
  50. 	out = 2LL*ans.x[1][1] + 4LL*ans.x[2][1] + 7LL*ans.x[3][1];
  51. 	printf("f(1234567890*1234567890) = %lld\n", out%MOD);
  52.  
  53. 	//f(1234567890^1234567890)
  54. 	ans = trans.pow(1234567890).pow(1234567890-1) * trans.pow(1234567890-1);
  55. 	out = 2LL*ans.x[1][1] + 4LL*ans.x[2][1] + 7LL*ans.x[3][1];
  56. 	printf("f(1234567890^1234567890) = %lld\n", out%MOD);
  57. }
  58.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
f(1234567890*1234567890) = 63703725
f(1234567890^1234567890) = 63703725
https://ideone.com/GXNpk0
language:
C++14 (gcc 8.3)
created:
7 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!