首页 > 代码库 > uva 12009 - Avaricious Maryanna(暴力)
uva 12009 - Avaricious Maryanna(暴力)
题目连接:uva 12009 - Avaricious Maryanna
题目大意;给定n,求x,x为n位数,并且x*x的后n位还是x。
解题思路:打个表会发现其实有规律,除了n=1的时候多了0和1,其他都是n-1位的基础上再新增一位数,1位的时候是5,6.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500;
int a[maxn+5], b[maxn+5];
int mul (int* p, int n) {
int q[maxn+5];
memset(q, 0, sizeof(q));
for (int i = 1; i < n; i++) {
int t = 0, flag = true;
for (int j = 1; j < n; j++) {
if (i + j - 1 > n) {
flag = false;
break;
}
t += p[i] * p[j] + q[i+j-1];
q[i+j-1] = t % 10;
t /= 10;
}
if (flag) {
int mv = i+n-1;
while (t) {
q[mv++] = t % 10;
t /= 10;
}
}
}
/*
for (int i = 1; q[i]; i++)
printf("%d", q[i]);
printf("\n");
*/
return q[n];
}
void init () {
a[1] = 5;
b[1] = 6;
mul(a, 2);
for (int i = 2; i <= maxn; i++) {
int ra = 0, rb = 0;
int p = mul(a, i);
int q = mul(b, i);
for (int k = 0; k <= 9; k++) {
if ((2 * k * a[1] + p) % 10 == k)
ra = k;
if ((2 * k * b[1] + q) % 10 == k)
rb = k;
}
a[i] = ra;
b[i] = rb;
}
}
void put (int* num, int n) {
printf(" ");
for (int i = n; i; i--)
printf("%d", num[i]);
}
int main () {
init();
int cas, n;
scanf("%d", &cas);
for (int k = 1; k <= cas; k++) {
scanf("%d", &n);
printf("Case #%d:", k);
if (n == 1)
printf(" 0 1");
if (a[n] && b[n]) {
if (a[n] > b[n]) {
put(b, n);
put(a, n);
} else {
put(a, n);
put(b, n);
}
} else if (a[n]) {
put(a, n);
} else if (b[n])
put(b, n);
printf("\n");
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。