fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. ll** matmul(ll** v1,ll** v2,ll M)
  6. {
  7. 	ll **c;
  8. 	c=(ll **)calloc(2,sizeof(long long));
  9. 	c[0]=(ll*)calloc(2,sizeof(long long));
  10. 	c[1]=(ll*)calloc(2,sizeof(long long));
  11. 	for(int i=0;i<2;i++)
  12. 	{
  13. 		for(int j=0;j<2;j++)
  14. 		{
  15. 			for(int k=0;k<2;k++)
  16. 			{
  17. 				c[i][j]=(c[i][j]+v1[i][k]*v2[k][j])%M;
  18. 			}
  19. 		}
  20. 	}
  21. 	return c;
  22. }
  23. ll** matpow(ll **v,ll n,int M) //variable pointer..
  24. {
  25.  
  26. 	ll **v2;
  27. 	v2=(ll **)calloc(2,sizeof(long long));
  28. 	v2[0]=(ll*)calloc(2,sizeof(long long));
  29. 	v2[1]=(ll*)calloc(2,sizeof(long long));
  30. 	for(int i=0;i<n;i++)
  31. 	{
  32. 		v2[i][i]=1;
  33. 	}
  34. 	while(n)
  35. 	{
  36. 		if(n%2)
  37. 			v2=matmul(v2,v,M);
  38. 		n/=2;
  39. 		v=matmul(v,v,M);
  40. 	}
  41. 	return v2;
  42. }
  43. int main()
  44. {
  45. 	int t,m;
  46. 	ll a,n,xx=1;
  47. 	cin>>t;
  48. 	for(int i=0;i<t;i++)
  49. 	{
  50. 		cin>>a>>n>>m;
  51. 		ll **v;
  52. 		v=(ll**)calloc(2,sizeof(long long));
  53. 		v[0]=(ll*)calloc(2,sizeof(long long));
  54. 		v[1]=(ll*)calloc(2,sizeof(long long));
  55.  
  56.  
  57. 		ll temp=a;int dig=0;
  58. 		while(temp!=0)
  59. 		{
  60. 			dig++;
  61. 			xx*=10;
  62. 			temp/=10;
  63. 		}
  64. 		v[0][0]=xx%m;
  65. 		v[0][1]=1;
  66. 		v[1][0]=0;
  67. 		v[1][1]=1;
  68. 		v=matpow(v,n-1,m); 
  69. 		cout<<((v[0][0]+v[0][1])%m*(a%m))%m<<endl;
  70.  
  71. 		xx=1;
  72. 	}
  73. 	return 0;
  74. }
Runtime error #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/h6YiDy
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!