fork download
copy 
  1. //By Jaskaran.Finding first k digits of N^N
  2. //Includes
  3. #include<iostream>
  4. #include <vector> 
  5. #include <queue>
  6. #include <map> 
  7. #include <set>
  8. #include <utility> //Pair
  9. #include <algorithm>
  10. #include <sstream> // istringstream>> ostring stream<<
  11. #include <iostream> 
  12. #include <iomanip> 
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <cstdlib>
  16. #include <ctime>
  17. #include <cstring>
  18. #include<cassert>
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22. typedef pair<int,int> ii;
  23. typedef vector<int> vi;
  24. typedef vector<bool> vb;
  25. typedef vector<ii> vii;
  26. typedef vector<vii> vvii;
  27. #define pb push_back
  28. #define mp make_pair
  29. #define ff first
  30. #define ss second
  31. #define rep(i,c,n) for(int i=c;i<n;i++)
  32. #define MAX(a,b) ((a)>(b)?(a):(b))
  33. #define MIN(a,b) ((a)<(b)?(a):(b))
  34.  
  35. const int p[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
  36. /* This function calculates (a^b)%MOD */
  37. ll power(int a, int b, int MOD)
  38. { ll x=1,y=a; 
  39. 	while(b > 0)
  40. 	{
  41. 		if(b%2 == 1)
  42. 		{
  43. 			x=(x*y);
  44. 			if(x>MOD) x%=MOD;
  45. 		}
  46. 		y = (y*y);
  47. 		if(y>MOD) y%=MOD; 
  48. 		b /= 2;
  49. 	}
  50. 	return x;
  51. }
  52. ll firstkdig(int N,int K)
  53. {long double a=N*log10l(N);//a=R+f where f is the fractional part
  54.  ll R=floor(a);
  55.  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
  56.  ll ans=floor(pow((long double)10,f+K-1));//as 10^f is a single digit
  57.  return ans;}
  58.  
  59. ll lastkdig(int N,int K)//N^N%(10^K+1)
  60. {
  61.  int MOD=p[K];
  62.  ll ans=power(N,N,MOD);
  63.  return ans;
  64. }
  65. int len(int num)
  66. {int c=0;
  67. if(num==0)
  68. return 1;
  69. while(num!=0)
  70. {num/=10;
  71.  c++;}
  72.  return c;
  73. }
  74. int main()
  75. {int T,N,K;
  76. scanf("%d",&T);
  77. while(T--)
  78. {scanf("%d%d",&N,&K);
  79.  ll ans1=firstkdig(N,K);
  80.  ll ans2=lastkdig(N,K);
  81.  printf("%lld ",ans1);
  82.  int l=len(ans2);//number of digits in ans2.This is to correct output in cases where the number of digits in ans2<K.We have to fix leading zeroes
  83.   rep(i,0,K-l)
  84.   printf("0");
  85.  printf("%lld\n",ans2);
  86. }
  87. return 0;
  88. }
Success #stdin #stdout 0s 2900KB
comments (?)
stdin
copy 
1
8 8
stdout
copy 
16777216 16777216
https://ideone.com/Qd65LD
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!