[UVA][大數開根號] 10606 - Opening Doors
21th June!! Holidays at last!!
That's what everyone in the school thought when the bell rang. It was time to leave the class and go away forever (or until September). Dima was running to the exit when he saw that paper on the wall:
Don't forget to
unlock all the lockers so that we can clean them in summer.
The principal.
Oh, no! Dima forgot to unlock it! So he had to go to the corridor where lockers were. When he got there, all the lockers had been already unlocked. Some of them were open and some of them were closed. Lockers were numbered from 1 to 90 (the number of boys in the school) and he had the last one. So he walked along the long corridor. While he reached his locker, he started to think why some of the doors were open and some closed. Then he invented a method to keep some open and some closed:
Once all the lockers were unlocked, the boy with locker number 1 opened all doors. Then the boy with locker number 2 closed the doors multiple of 2. Then the boy with locker number 3 changed the status of all doors multiple of 3 (he opens doors 6,12...and he closes doors 3, 9...)...and until everyone, including Dima, had done so.
Now he wants to know whether that was what happened or not. As a first-sight method, he wants to see if the door with the biggest number that is open matches the door with the biggest number that keeps open using his method. That's where he needs your help. He could do it by hand, but he also wants to check it next year (and the number of students may change), so he asked you for a program that simulates it for any number of students.
Each line in the input will contain a single number N (1≤N≤10^100), indicating the number of boys in the school (you never know what the number of students will be if Earth population keeps growing...).
Input will be terminated by a test case with N=0. That line shouldn't be processed. For each line in the input, write a line with the number of the door with the biggest number that keeps open.
|
Sample Input |
Sample Output |
|
1 90 0 |
1 81 |
Problem author: Carlos M. Casas Cuadrado
Problem submitter: Carlos M. Casas Cuadrado
Problem solution: Carlos M. Casas Cuadrado
使用中國開方法
將之前的代碼重新修正。
// 0.068 s
#include <stdio.h>
#include <string.h>
int main() {
char s[1024];
while(scanf("%s", s) == 1) {
if(!strcmp(s, "0"))
break;
int len = strlen(s);
int x[100] = {}, y[100] = {};
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;
long long ret[100] = {}, retidx = 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) {
ret[retidx++] = 0;
continue;
}
int l = 0, r = 9999, p;
int z[100] = {}; // 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;
}
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--;
ret[retidx++] = p;
}
long long ans[100] = {};
int p, q;
for(i = retidx-1, p = 0; i >= 0; i--, p++) {
if(ret[i])
for(j = retidx-1, q = 0; j >= 0; j--, q++) {
ans[p+q] += ret[i]*ret[j];
}
}
retidx <<= 1;
retidx++;
for(i = 0; i < retidx; i++) {
if(ans[i] >= 10000) {
ans[i+1] += ans[i]/10000;
ans[i] %= 10000;
}
}
while(ans[retidx] == 0) retidx--;
printf("%lld", ans[retidx]);
for(i = retidx-1; i >= 0; i--)
printf("%04lld", ans[i]);
puts("");
}
return 0;
}