2012-12-28 22:10:25Morris
[UVA][大數] 12505 - Searching in sqrt(n)
Searching in sqrt(n)
| 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 (T
100), 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;
}