fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. #define si(X) scanf("%d", &(X))
  6. #define sll(X) scanf("%lld",&(X))
  7.  
  8. const ll mod = 1e18+7;
  9. ll expo(ll base , ll pow , ll n){
  10.     ll ans = 1;
  11.     while(pow!=0){
  12.         if(base > n || base <= 0){
  13.             return -1;
  14.         }
  15.         if(pow&1==1){
  16.         	if(ans > n/base) return -1;
  17.             ans = ans*base;
  18.             if(ans > n|| ans <= 0){
  19.                 return -1;
  20.             }
  21.             //ans = ans%mod;
  22.         }
  23.         if(base > n/base) base = mod;
  24.         else
  25.         	base *= base;
  26.        // base%=mod;
  27.         pow/=2;
  28.  
  29.     }
  30.     return ans;
  31. }
  32.  
  33. /* -------Template ends here-------- */
  34.  
  35. const int M = 100001;
  36.  
  37.  
  38. int fits(ll base , int dig , ll n){
  39.     for(int i = dig - 1 ; i>=0 ; i--){
  40.         ll temp = expo(base , i , n);
  41.         if(temp == -1)
  42.             return -1;
  43.         n -= temp;
  44.         if(n<0)
  45.             return -1;
  46.     }
  47.     if(n == 0)
  48.         return 0;
  49.     return 1;
  50. }
  51. int main(){
  52.  
  53. 	int t;
  54. 	si(t);
  55.  
  56. 	for(int alp = 1;alp<=t;alp++){
  57.  
  58.         ll n;
  59.         sll(n);
  60.         ll ans = n - 1;
  61.         int dig = 1;
  62.  
  63.         for(int digits = 70 ; digits >= 2 ; digits--){
  64.             ll lo = 2 , hi = n - 1;
  65.             int o = 0;
  66.             while(lo <= hi){
  67.                 ll mid = (lo + hi + 1)/2;
  68.                 int num = fits(mid , digits , n);
  69.                 if(num == 0){
  70.                     ans = mid;
  71.                     o++;
  72.                     break;
  73.                 }
  74.                 else if(num == 1){                     // this base is small
  75.                     lo = mid + 1;
  76.                 }
  77.                 else{                                // this base is large
  78.                     hi = mid - 1;
  79.                 }
  80.             }
  81.             if(o){
  82.                 break;
  83.             }
  84.         }
  85.  
  86.  
  87.  
  88.  
  89.  
  90. 		cout<<"Case #"<<alp<<": "<<ans<<endl;
  91.  
  92. 	}
  93.  
  94. }
Success #stdin #stdout 0.02s 3476KB
comments (?)
stdin
copy 
100
14919921443713777
16035713712910627
470988884881403701
663208457429249320
35417244247309081
18912140357306197
821424692950225218
194148123592167400
169683965173070355
30896151154490161
8152332946963171
26504196177401065
727004545306745403
1000000000000000000
210724372007205925
230839591399678411
139782788180007861
31108559476176585
70640308161049884
919818571896748567
805068181058041870
528077080918778560
3392264354546656
172589956609631527
752116768933572174
278385972618095971
500364605967785712
936501597464173890
5346848976102943
42711799474754936
39739406344976521
96642126154887385
507373618559718949
148522861921131118
5990709545080807
58873926717610501
779668738937986840
34824506845925071
131226544799105148
14500751095055161
541064907662839644
665930169964312773
2854907964745564
151970818238211610
916365355264637559
353896329635329936
625318600331879360
690683275350237133
31899883679471306
99670604181093725
736827088955709913
113836064401097977
8508110325218143
13321050162245608
609649911611389831
46268622795238201
468339557884957084
25965247599543841
381252133354068211
494196153725539231
945648548682242665
19337682799995045
619861907468053901
229239004074282805
386581418747680
610260633162639678
299694296458966143
845078653019833051
373345485670171062
27233228344819564
129023667184858285
83124300916686757
379255974823102021
245249591795535097
43969534069696
66722517469920
9858438270839893
6910943299863520
25717131834499624
92023103018361641
943990493461794871
513767149194597040
112064524403878803
174210760090244515
5811353213141560
85718519097865885
984245729893369243
516227865362638410
106954294285992115
58860842632125700
446401559469368954
900075818947323940
813918209914834753
803117911029730313
130463899351376137
6980452392892987
66613711011280280
311119354403376793
114349900145584129
182859777940000980
stdout
copy 
Case #1: 496
Case #2: 502
Case #3: 686286299
Case #4: 872067
Case #5: 117
Case #6: 516
Case #7: 821424692950225217
Case #8: 579043
Case #9: 553622
Case #10: 560
Case #11: 90290270
Case #12: 298152
Case #13: 727004545306745402
Case #14: 999999999999999999
Case #15: 84
Case #16: 480457689
Case #17: 373875364
Case #18: 314504
Case #19: 413381
Case #20: 986
Case #21: 805068181058041869
Case #22: 808287
Case #23: 150255
Case #24: 746
Case #25: 752116768933572173
Case #26: 527622945
Case #27: 500364605967785711
Case #28: 936501597464173889
Case #29: 418
Case #30: 42711799474754935
Case #31: 584
Case #32: 458904
Case #33: 507373618559718948
Case #34: 148522861921131117
Case #35: 426
Case #36: 242639499
Case #37: 779668738937986839
Case #38: 45
Case #39: 131226544799105147
Case #40: 120419064
Case #41: 541064907662839643
Case #42: 665930169964312772
Case #43: 141861
Case #44: 81
Case #45: 971306
Case #46: 707335
Case #47: 625318600331879359
Case #48: 690683275350237132
Case #49: 31899883679471305
Case #50: 268
Case #51: 858386328
Case #52: 696
Case #53: 92239418
Case #54: 201
Case #55: 847930
Case #56: 599
Case #57: 776581
Case #58: 544
Case #59: 725110
Case #60: 889
Case #61: 981544
Case #62: 212
Case #63: 619861907468053900
Case #64: 21881
Case #65: 72847
Case #66: 610260633162639677
Case #67: 547443418
Case #68: 174
Case #69: 373345485670171061
Case #70: 300861
Case #71: 505308
Case #72: 288312852
Case #73: 615837620
Case #74: 791
Case #75: 35295
Case #76: 40559
Case #77: 99289668
Case #78: 183
Case #79: 295171
Case #80: 92023103018361640
Case #81: 980970
Case #82: 800919
Case #83: 334760398
Case #84: 558502
Case #85: 179787
Case #86: 76
Case #87: 992091593
Case #88: 516227865362638409
Case #89: 474678
Case #90: 388993
Case #91: 446401559469368953
Case #92: 900075818947323939
Case #93: 31
Case #94: 803117911029730312
Case #95: 712
Case #96: 437
Case #97: 253
Case #98: 823
Case #99: 485376
Case #100: 37
https://ideone.com/ofEZLS
my template :)
language:
C++14 (gcc 8.3)
created:
8 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!