fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. char X[1005], Y[1005], Z[505], A[505];
  5.  
  6. int main() {
  7.     int cases;
  8.     scanf("%d", &cases);
  9.     while(cases-- > 0) {
  10.         scanf("%s", X);
  11.         int X_right_end = strlen(X);
  12.         int X_pivot_left = 0;
  13.         int X_pivot_right = 2;
  14.         if(X_right_end % 2 != 0) {
  15.             X_pivot_right = 1;
  16.         }
  17.         int Z_pivot_right = 2;
  18.         int Z_pivot_left = 1;
  19.         int Y_pivot_left = -1;
  20.         int Y_pivot_right = -1;
  21.         int A_right_end = 1;
  22.  
  23.         for(int i = 0; i < X_right_end; ++i) {
  24.             X[i] -= '0';
  25.         }
  26.         for(int i = 0; i < 505; ++i) {
  27.             Z[i] = 0;
  28.         }
  29.  
  30.         do {
  31.             while(true) {
  32.                 int up = 9, bottom = 0;
  33.                 int k = (up + bottom) / 2;
  34.                 bool break_loop = false;
  35.                 bool the_same_length = false;
  36.                 bool X_bigger_than_Y = false;
  37.                 while(true) {
  38.                     Z[Z_pivot_right - 1] = k;
  39.                     int carry_num = 0, i, j;
  40.                     Y_pivot_right = X_pivot_right;
  41.                     for(i = Z_pivot_right - 1, j = Y_pivot_right - 1; i >= Z_pivot_left; --i, --j) {
  42.                         int mul = Z[i] * k + carry_num;
  43.                         carry_num = mul / 10;
  44.                         Y[j] = mul % 10;
  45.                     }
  46.                     if(carry_num != 0) {
  47.                         if(j < 0 || j < X_pivot_left) {
  48.                             the_same_length = false;
  49.                             X_bigger_than_Y = false;
  50.                         } else if(j >= X_pivot_left) {
  51.                             Y[j] = carry_num;
  52.                             Y_pivot_left = j;
  53.                             for(int zero = X_pivot_left; zero < Y_pivot_left; ++zero) {
  54.                                 Y[zero] = 0;
  55.                             }
  56.                             the_same_length = true;
  57.                             X_bigger_than_Y = true;
  58.                         }
  59.                     } else if(carry_num == 0) {
  60.                         if(j < X_pivot_left - 1) {
  61.                             the_same_length = false;
  62.                             X_bigger_than_Y = false;
  63.                         } else if(j >= X_pivot_left - 1) {
  64.                             Y_pivot_left = j + 1;
  65.                             for(int zero = X_pivot_left; zero < Y_pivot_left; ++zero) {
  66.                                 Y[zero] = 0;
  67.                             }
  68.                             the_same_length = true;
  69.                             X_bigger_than_Y = true;
  70.                         }
  71.                     }
  72.                     if(break_loop) {
  73.                         break;
  74.                     }
  75.                     if(X_bigger_than_Y) {
  76.                         for(int i = X_pivot_left, j = X_pivot_left; i < X_pivot_right; ++i, ++j) {
  77.                             if(X[i] < Y[j]) {
  78.                                 X_bigger_than_Y = false;
  79.                                 break;
  80.                             } else if(X[i] > Y[j]) {
  81.                                 break;
  82.                             }
  83.                         }
  84.                     }
  85.                     if(X_bigger_than_Y) {
  86.                         if(up == bottom) {
  87.                             break_loop = true;
  88.                             continue;
  89.                         }
  90.                         bottom = k + 1;
  91.                         if(up < bottom) {
  92.                             bottom = up;
  93.                         }
  94.                         k = (up + bottom) / 2;
  95.                     } else {
  96.                         if(up == bottom) {
  97.                             k -= 1;
  98.                             if(k < 0) {
  99.                                 k = 0;
  100.                             }
  101.                             break_loop = true;
  102.                             continue;
  103.                         }
  104.                         up = k - 1;
  105.                         if(up < bottom) {
  106.                             up = bottom;
  107.                         }
  108.                         k = (up + bottom) / 2;
  109.                     }
  110.                 }
  111.                 if(k > 0) {
  112.                     for(int i = X_pivot_right - 1; i >= X_pivot_left; --i) {
  113.                         X[i] -= Y[i];
  114.                         if(X[i] < 0) {
  115.                             X[i] += 10;
  116.                             X[i - 1] -= 1;
  117.                         }
  118.                     }
  119.                 }
  120.                 X_pivot_right += 2;
  121.                 Z[Z_pivot_right - 1] += k;
  122.                 int i, carry_num = 0;
  123.                 for(i = Z_pivot_right - 1; i >= Z_pivot_left; --i) {
  124.                     if(Z[i] >= 10) {
  125.                         Z[i] -= 10;
  126.                         Z[i - 1] += 1;
  127.                         carry_num = 1;
  128.                     } else {
  129.                         carry_num = 0;
  130.                     }
  131.                 }
  132.                 if(carry_num != 0) {
  133.                     Z_pivot_left -= 1;
  134.                 }
  135.                 Z[Z_pivot_right] = 0;
  136.                 Z_pivot_right += 1;
  137.                 while(X_pivot_left < X_pivot_right && 
  138.                     (X_pivot_right - X_pivot_left) > (Z_pivot_right - Z_pivot_left)) {
  139.                     if(X[X_pivot_left] == 0) {
  140.                         ++X_pivot_left;
  141.                     } else {
  142.                         break;
  143.                     }
  144.                 }
  145.                 A[A_right_end - 1] = (char)(k + '0');
  146.                 A_right_end += 1;
  147.                 break;
  148.             }
  149.         } while(X_pivot_right <= X_right_end);
  150.  
  151.         A[A_right_end - 1] = 0;
  152.         puts(A);
  153.  
  154.         if(cases > 0) {
  155.             puts("");
  156.         }
  157.     }
  158. }
Success #stdin #stdout 0s 2900KB
comments (?)
stdin 
2
10000200001
4294967296
stdout 
100001

65536
https://ideone.com/lAR5Cz
language:
C++ (gcc 8.3)
created:
12 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!