UVA 12009 - Avaricious Maryanna
题意：给定一个n。求出n个数位组成的数字x，x^2的前面|x|位为x
思路：自己先暴力打了前几组数据，发现除了1中有0和1以外，其它数据都是由前一项往上再加入一位得到的，因此设新数字为(a∗10k+x)2=(a∗10k)2+x2+2∗a∗10k∗x
因此(a∗10k+x)=((a∗10k)2+x2+2∗a∗10k∗x)/10k%10
化简后得到x2/10k%10+2∗a∗x%10
因此仅仅要能求出x2/10k%10。然后再枚举a(0
<= a <= 9)，去推断一下符合不符合，符合就加到前面一位就可以。然后就先预处理出500位的答案。
那么如今问题仅仅剩下x2/10k%10这个的解。这个值是等于x^2后|x|
+ 1位上的数字，模拟高精度乘法求出就可以
代码：
#include <stdio.h>
#include <string.h> int t, n;
char a[505], b[505];
int ans[505], num[505]; int cal(char *str) {
memset(ans, 0, sizeof(ans));
int len = strlen(str);
for (int i = len - 1; i >= 0; i--)
num[len - i - 1] = str[i] - '0';
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (i + j > len) continue;
ans[i + j] += num[i] * num[j];
}
}
for (int i = 0; i < len; i++) {
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;
}
return ans[len];
} void init() {
a[500] = '\0'; b[500] = '\0';
a[499] = '5'; b[499] = '6';
for (int i = 498; i >= 0; i--) {
int aa = cal(a + i + 1);
int bb = cal(b + i + 1);
for (int j = 0; j < 10; j++) {
if ((2 * j * 5 + aa) % 10 == j)
a[i] = j + '0';
if ((2 * j * 6 + bb) % 10 == j)
b[i] = j + '0';
}
}
} int main() {
init();
int cas = 0;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
printf("Case #%d:", ++cas);
if (n == 1) printf(" 0 1 5 6\n");
else {
if (a[500 - n] == '0' && b[500 - n] == '0') printf("Impossible\n");
else if (a[500 - n] == '0') printf(" %s\n", b + 500 - n);
else if (b[500 - n] == '0') printf(" %s\n", a + 500 - n);
else {
if (strcmp(a + 500 - n, b + 500 - n) < 0) printf(" %s %s\n", a + 500 - n, b + 500 - n);
else printf(" %s %s\n", b + 500 - n, a + 500 - n);
}
}
}
return 0;
}