fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cctype>
  4. #include <vector>
  5. #include <cstdlib>
  6. #include <csignal>
  7. using namespace std;
  8.  
  9.  
  10. string errinfo; void sh(int s) {cerr << errinfo; exit(1);}
  11.  
  12. struct huge {vector<char>num; huge();};
  13. huge::huge():num(102,0){}
  14.  
  15. inline string out(huge output);
  16.  
  17.  
  18. inline huge hmax () {errinfo="hmax\n";huge res;for(int i=0;i<102;++i) res.num[i]=9; return res;}
  19. inline bool comp (huge a, huge b) {errinfo="comp "; errinfo+=out(a); errinfo+=' '; errinfo+=out(b); return (a.num==b.num);}
  20. inline bool even (huge n) {errinfo="even "; errinfo+=out(n); return (n.num[101]%2==0);}
  21. inline bool zero (huge n)
  22. {errinfo="zero "; errinfo+=out(n);for(int i=0;i<102;++i) if(n.num[i]!=0) return false; return true;}
  23.  
  24. inline bool grtr (huge a, huge b)
  25. {
  26.     errinfo="grtr "; errinfo+=out(a); errinfo+=' '; errinfo+=out(b);
  27.     for(int i=0;i<102;++i)
  28.     {
  29.         if(a.num[i]>b.num[i]) return true;
  30.         if(a.num[i]<b.num[i]) return false;
  31.     }
  32.     return false;
  33. }
  34.  
  35. inline huge decr(huge n)
  36. {
  37.     errinfo="decr "; errinfo+=out(n);
  38.     for(int i=101;i>=0;--i)
  39.         if(n.num[i]>0) {--n.num[i]; return n;}
  40.         else n.num[i]=9;
  41.     return n;
  42. }
  43.  
  44. inline huge incr(huge n)
  45. {
  46.     errinfo="incr "; errinfo+=out(n);
  47.     for(int i=101;i>=0;--i)
  48.         if(n.num[i]<9) {++n.num[i]; return n;}
  49.         else n.num[i]=0;
  50.     return n;
  51. }
  52.  
  53. inline huge div2(huge n)
  54. {
  55.     errinfo="div2 "; errinfo+=out(n);
  56.     for(int i=101;i>=0;--i)
  57.         if(n.num[i]%2==0) n.num[i]/=2;
  58.         else
  59.         {
  60.             n.num[i]/=2; n.num[i+1]+=5;
  61.             if(n.num[i+1]>=10) {n.num[i+1]-=10; n.num[i]+=1;}
  62.         }
  63.         return n;
  64. }
  65.  
  66. inline huge addc (huge a, huge b)
  67. {
  68.     errinfo="addc "; errinfo+=out(a); errinfo+=' '; errinfo+=out(b);
  69.     for(int i=101;i>=0;i--)
  70.     {a.num[i]+=b.num[i]; if(a.num[i]>=10) {a.num[i]-=10; a.num[i-1]+=1;}}
  71.     return a;
  72. }
  73.  
  74. inline huge mult (huge a, huge b)
  75. {
  76.     errinfo="mult "; errinfo+=out(a); errinfo+=' '; errinfo+=out(b);
  77.     huge res;
  78.     for(int i=101;i>=0;--i) if(a.num[i]!=0)
  79.     for(int j=101;j>=0;--j) if(b.num[j]!=0)
  80.     {
  81.         huge hlp;
  82.         if(i+j-101<0) return (hmax());
  83.         hlp.num[i+j-101]=(a.num[i]*b.num[j])%10;
  84.         if((a.num[i]*b.num[j])/10!=0)
  85.             if(i+j-102<0) return (hmax());
  86.             else hlp.num[i+j-102]=(a.num[i]*b.num[j])/10;
  87.         res=addc(res,hlp);
  88.     }
  89.     return res;
  90. }
  91.  
  92. inline huge itoh(int n)
  93. {errinfo="itoh "; errinfo+=out(itoh(n));huge res; for(int i=0;n>0;++i) {res.num[101-i]=n%10; n/=10;} return res;}
  94.  
  95. inline huge pow(huge k, huge n)
  96. {
  97.     errinfo="pow "; errinfo+=out(k); errinfo+=' '; errinfo+=out(n);
  98.     if(zero(n)) return itoh(1);
  99.     if(!even(n))
  100.     {return mult(k,pow(k,decr(n)));}
  101.     huge hlp=pow(k,div2(n)); return mult(hlp,hlp);
  102. }
  103.  
  104. inline huge mean (huge a, huge b)
  105. {errinfo="mean "; errinfo+=out(a); errinfo+=' '; errinfo+=out(b);huge res=addc(a,b); if(!even(res)) res=decr(res); res=div2(res); return res;}
  106.  
  107. inline huge stoh(string input)
  108. {
  109.     errinfo="stoh "; errinfo+=input;
  110.     huge res;
  111.     for(int i=input.size()-1;i>=0;--i)
  112.         res.num[102-input.size()+i]=int(input[i]-'0');
  113.     return res;
  114. }
  115.  
  116. inline huge read(void)
  117. {
  118.     errinfo="read";
  119.     string res;
  120.     while(!isdigit(cin.peek())) cin.ignore();
  121.     char hlp=cin.get(); while(isdigit(hlp)) {res+=hlp; hlp=cin.get();}
  122.     return stoh(res);
  123. }
  124.  
  125. inline string out(huge output)
  126. {
  127.     int i=0; while(output.num[i]==0) ++i;
  128.     string res; for(;i<102;++i) res+=char('0'+output.num[i]);
  129.     return res;
  130. }
  131.  
  132. huge wysz (huge n, huge p)
  133. {
  134.     errinfo="wysz "; errinfo+=out(n); errinfo+=' '; errinfo+=out(p);
  135.     huge a=itoh(1); huge b=incr(p);
  136.     huge res=mean(a,b); cerr << out(a) << '\t' << out(res) << '\t' << out(b) << '\n';
  137.     huge hlp; hlp=pow(res,n);
  138.     while(!comp(hlp,p))
  139.     {
  140.         if(grtr(hlp,p)) b=res;
  141.         else a=res;
  142.         res=mean(a,b); cerr << out(a) << '\t' << out(res) << '\t' << out(b) << '\n';
  143.         hlp=pow(res,n);
  144.     }
  145.     return res;
  146. }
  147.  
  148. int main()
  149. {
  150.     errinfo="main"; signal(SIGABRT,sh);
  151.     ios_base::sync_with_stdio(false);
  152.     int n; while(cin >> n) cout << out(wysz(itoh(n),read())) << '\n';
  153.     return 0;
  154. }
Runtime error #stdin #stdout 0.02s 11120KB
comments (?)
stdin
copy 
7
4357186184021382204544
stdout
copy 
Standard output is empty
https://ideone.com/riFOOa
language:
C++ (gcc 8.3)
created:
10 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!