Searching in sqrt(n)

In binary, the square root of 2, denoted by sqrt(2), is an infinite number 1.0110101000001001111...

Given an integer n and a binary string (i.e. a string consisting of 0 and 1) S, your task is to find the first occurrence of S in the fraction part (i.e. the part after the decimal point) of sqrt(n). In case sqrt(n) is an integer, the fraction part is an infinite sequence of zeros.

Input 

The first line contains T (T100), the number of test cases. Each of the following lines contains an integer n ( 2n1, 000, 000) and a binary string S with at most 20 characters.

Output 

For each case, print the position of the first character in the first occurrence of S. The first digit after the dot is at position 0. The answer is guaranteed to be no greater than 100.

Sample Input 

2
2 101
1202 110011

Sample Output 

2
58

---

Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Feng Chen, Jane Alam Jan

還是將 sqrt(n) 的二進制找出來吧。
中國直式開方法在二進制中我就不太會用了，那麼一位一位窮舉，接著使用大數乘法比大小，
依序將二進制的 sqrt(n) 找出來。
由於答案已經說明會在 100 以內，但又 |S| = 20，那還是計算 120 位小數點之後的所有值。


#include <stdio.h>
#include <math.h>
#include <string.h>
short bin[160], mbin[320], obin[320];
int check(int st) {
    int i, j;
    memset(mbin, 0, sizeof(mbin));
    for(i = st; i < 160; i++) {
        if(bin[i])
        for(j = st; j < 160; j++)
            mbin[i+j] += bin[i]&bin[j];
    }
    for(i = 0; i < 320; i++) {
        if(mbin[i] >= 2) {
            mbin[i+1] += mbin[i]>>1;
            mbin[i] &= 1;
        }
    }
    /*for(i = 319; i >= 0; i--)
        printf("%d", mbin[i]);
    puts("");
    for(i = 319; i >= 0; i--)
        printf("%d", obin[i]);
    puts("");*/
    for(i = 319; i >= 0; i--)
        if(mbin[i] > obin[i])
            return 0;
        else if(mbin[i] < obin[i])
            return 1;
    return 1;
}
int main() {
    scanf("%*d");
    int n, i, j;
    char s[50];
    while(scanf("%d %s", &n, s) == 2) {
        int sq = sqrt(n);
        memset(bin, 0, sizeof(bin));
        memset(obin, 0, sizeof(obin));
        for(i = 10; i >= 0; i--)
            bin[150-(10-i)] = (sq>>i)&1;
        for(i = 25; i >= 0; i--)
            obin[305-(25-i)] = (n>>i)&1;
        /*for(i = 150; i >= 140; i--)
            printf("%d", bin[i]);
        puts("");*/
        for(i = 139; i >= 0; i--) {
            bin[i] = 1;
            if(check(i)) {}
            else    bin[i] = 0;
        }
        for(i = 139; i >= 0; i--) {
            for(j = 0; s[j]; j++)
                if(s[j]-'0' != bin[i-j])
                    break;
            if(s[j] == '\0') {
                printf("%d\n", 139-i);
                break;
            }
        }
        /*printf(".");
        for(i = 139; i >= 0; i--)
            printf("%d", bin[i]);
        puts("");*/
    }
    return 0;
}