Square root

The Problem

You are to determinate X by given Y, from expression

The Input

The first line is the number of test cases, followed by a blank line.

Each test case of the input contains a positive integer Y (1<=Y<=10¹⁰⁰⁰),with no blanks or leading zeroes in it.
It is guaranteed, that for given Y, X will be always an integer.

Each test case will be separated by a single line.

The Output

For each test case, your program should print X in the same format as Y was given in input.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

1
7206604678144

Sample Output

2684512

---

Alex Gevak
September 10, 2000 (Revised 2-10-00, Antonio Sanchez)

中國直式開方法的操作約如下。

951*951=904401

               9, 5, 1 
             ----------
   口->9     |90,44,01
+  口->9      81
-----         --------
  18口->5       9,44,01
  + 口->5       9,25 
------          -------
  190口->1        19,01
+    口->1        19,01
---------        ------
  1902                0

105*105=11025

              1, 0, 5
  口->1      ----------
+ 口->1      |1,10,25
-------       1
  2口->0      ---------
+  口->0        10,25
--------        10,25
  20口->5     ------- 
+   口->5           0
--------
  210

如果是以十進制的方式去做，很明顯地可以可以慢慢找到框框中要填哪個數字，
但最慘的情況，仍是需要 O(10)，如果用二分搜尋， O(3)，以數字平均的 O(5) 還要低一些，

因此速度會稍微快一點。

但很明顯地會發現這個做法在百進制也是行得通的，但這時候就必須猜框框中的數字是在 [0,99]。

而在二分搜尋的效率上並沒有加快，但是在乘法的效率上會上升兩倍。

最後為了不超過 int 的範圍，最多使用 10000 進制。

---

//0.084 s Rank 10

#include <stdio.h>
#include <string.h>

int main() {
    char s[1024];
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        int len = strlen(s);
        int x[300] = {}, y[300] = {};
        int i, j;
        for(i = 0, j = len-1; j >= 0; i++) {
            x[i] = s[j]-'0';
            if(j-1 >= 0)    x[i] = x[i] + (s[j-1]-'0')*10;
            if(j-2 >= 0)    x[i] = x[i] + (s[j-2]-'0')*100;
            if(j-3 >= 0)    x[i] = x[i] + (s[j-3]-'0')*1000;
            j -= 4;
        }
        int xlen = len, ylen = 0, head = 0;
        while(xlen >= 0 && x[xlen] == 0) xlen--;
        for(j = (len-1)/8, i = j*2; j >= 0; j--, i -= 2) {
            ylen++;
            for(int p = ylen; p >= 1; p--)
                y[p] = y[p-1];
            y[0] = 0;
            if(xlen < j) {
                if(!head)   putchar('0'), head = 1;
                else {
                    printf("%04d", 0);
                }
                continue;
            }
            int l = 0, r = 9999, p;
            int z[300]; // z = (y*10 + p)*p;
            while(l <= r) {
                p = (l+r)/2;
                y[0] += p;
                z[0] = 0;
                for(int q = 0; q <= ylen+5; q++) {
                    z[q] += p*y[q];
                    z[q+1] = z[q]/10000;
                    z[q] %= 10000;
                }
                /*printf("loop %d\n", p);
                for(int q = ylen+2; i+q >= 0; q--)
                    printf("%02d", x[i+q]);
                puts(" x");
                for(int q = ylen+2; q >= 0; q--)
                    printf("%02d", z[q]);
                puts(" z");*/
                int chflag = 0;
                for(int q = ylen+5; q >= 0; q--) {
                    if(z[q] > x[i+q]) {
                        chflag = 1;
                        break;
                    } else if(z[q] < x[i+q]) {
                        chflag = 0;
                        break;
                    }
                }
                y[0] -= p;
                if(chflag)
                    r = p-1;
                else
                    l = p+1;
            }
            p = l-1;
            y[0] = p;
            z[0] = 0;
            for(int q = 0; q <= ylen+5; q++) {
                z[q] += p*y[q];
                z[q+1] = z[q]/10000;
                z[q] %= 10000;
            }
            for(int q = ylen+5; q >= 0; q--)
                x[i+q] -= z[q];
            for(int q = 0; q <= ylen+5; q++) {
                while(x[i+q] < 0)
                    x[i+q] += 10000, x[i+q+1]--;
            }
            y[0] += p;
            for(int q = 0; q <= ylen+5; q++) {
                if(y[q] >= 10000) {
                    y[q+1] += y[q]/10000;
                    y[q] %= 10000;
                }
            }
            ylen += 5;
            while(ylen >= 0 && y[ylen] == 0)    ylen--;
            while(xlen >= 0 && x[xlen] == 0)    xlen--;
            if(!head)   printf("%d", p), head = 1;
            else        printf("%04d", p);
        }
        puts("");
        if(t)
            puts("");
    }
    return 0;
}