首页 > 代码库 > UVA 12009 - Avaricious Maryanna(数论)
UVA 12009 - Avaricious Maryanna(数论)
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; }
UVA 12009 - Avaricious Maryanna(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。