fork download
copy 
  1. #include<iostream>	
  2. #include<stdio.h>
  3. #include<math.h>
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. long long  LastKDigitsModularExponetiation( long long  base,long long exponent,double mod);
  8. ll firstkdig(int N,int K)
  9. {
  10. 	long double a=N*log10l(N);//a=R+f where f is the fractional part
  11.  	ll R=floor(a);
  12.  	long double f=a-R;//Since n^n=10^a=10^R*10^f 10^R doesn't decide the first k digits.its only 10^f which decides first k digits
  13.  	ll ans=floor(pow((long double)10,f+K-1));//as 10^f is a single digit
  14.  	return ans;
  15. }
  16. int length(int n)
  17. {
  18. 	if(n==0)
  19. 	return 1;
  20. 	int len=0;
  21. 	while(n!=0)
  22. 	{
  23. 		n=n/10;
  24. 		len++;
  25. 	}
  26. 	return len;
  27. }
  28. int main()
  29. {
  30.  
  31. 	int test;
  32. 	scanf("%d",&test);
  33. 	while(test--)
  34. 	{
  35. 		int n, k;
  36. 		scanf("%d%d",&n,&k);
  37.  
  38. 		ll ans=firstkdig(n,k);
  39.  
  40. 		//cout<<"HELO"<<pow(10,k);
  41.  
  42.  
  43. 		int t1=length((int)ans);
  44. 		if(t1!=k)
  45. 		{
  46. 			for(int i=1;i<=k-t1;i++)
  47. 				printf("0");
  48. 		}
  49. 		printf("%lld ",ans);
  50. 		long long ans2=LastKDigitsModularExponetiation(n,n,pow(10,k));
  51. 		t1=length((int)ans2);
  52. 		if(t1!=k)
  53. 		{
  54. 			for(int i=1;i<=k-t1;i++)
  55. 				printf("0");
  56. 		}
  57. 		printf("%lld\n",(long long )ans2);
  58. 	}
  59. 	return 0;
  60. }
  61. /*
  62. long int LastKDigitsModularExponetiation(long int base,long int exponent,long double mod)
  63. {
  64. 	long int res=1;
  65. 	//cout<<res<<endl;
  66. 	for(int i=0;i<exponent;i++)
  67. 	{
  68. 		res=(res*base);
  69. 		//cout<<res<<"\t";
  70. 		res%=int(mod);
  71. 		//cout<<res<<endl;
  72. 	}
  73. 	//cout<<res<<endl;
  74. 	return res;
  75. }*/
  76. long long LastKDigitsModularExponetiation(long long base, long long  exponent, double mod){
  77.     if (exponent == 0){return 1;}
  78.     if (exponent == 1){return (long long )base % (long long )mod;}
  79.     if ((long long)exponent % 2 == 1){
  80.         return (((long long )(base) % (long long )mod) *(long long ) LastKDigitsModularExponetiation(base, exponent-1, mod)) % (long long )mod;
  81.     }
  82.     else{
  83.         long double newBase = LastKDigitsModularExponetiation(base, exponent / 2, mod);
  84.         return (long long )(newBase * newBase) %(long long) mod;
  85.     }
  86. }
Success #stdin #stdout 0s 2900KB
comments (?)
stdin
copy 
1
8 8
stdout
copy 
16777215 16777216
https://ideone.com/lIZ20o
language:
C++ (gcc 8.3)
created:
10 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!