 2018-11-06 13:20

# 自我复制数字的程序，这个算法怎么用C语言

Problem Description
Sherlock is fond of playing with numbers. Two days ago he discovered that 9376^2 = 87909376 - the last four digits constitute 9376 again. He called such numbers self-replicating.

More precisely, an n-digit number is called self-replicating if it is equal to the number formed by the last n digits of its square. Now Sherlock often asks Xay to help him to find new such numbers. To make the things worse, Sherlock already knows what the scales of notation are, so he asks Xay to find, for example, hexadecimal or binary self-replicating numbers.

Xay wants to help Sherlock, but unfortunately he is very busy now: he is seriously preparing and training for the next ACM Regional Contest. So he asked you to write a program that for a given base b and length n will find all n-digit self-replicating numbers in the scale of notation with base b.

Input
there are multiple test cases. one line of each test case contains two integer numbers b and n separated by a single space, the base b of the scale of notation (2 ≤ b ≤ 36) and the required length n (1 ≤ n ≤ 2000).

Output
For eacho test case, the first line contains K - the total number of self-replicating numbers of length n in base b. Next K lines contain one n-digit number in base b each. Uppercase Latin letters from A to Z must be used to represent digits from 10 to 35. The self-replicating numbers should be output int lexicographic order.

Sample Input
2 1
10 4

Sample Output
2
0
1
1
9376

• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 2条回答默认 最新

• 不行了，脑壳疼=.=

`````` #include<stdio.h>
#include<string.h>
#include<math.h>
char* trans(char *a) {
char ch;
int len = strlen(a);
for (int i = 0; i < len/2; i++) {
ch = a[i];
a[i] = a[len - i - 1];
a[len - i - 1] = ch;
}
return a;
}
char* add(char a[], char b[],int key) {       //把2个字符串相加
while (strlen(a) != strlen(b)) {
int al = strlen(a), bl = strlen(b);
if (al > bl)
b[bl] = '0';
else
a[al] = '0';
a[al + 1] = b[bl + 1] = '\0';
}
a[strlen(a)] = b[strlen(b)] = '\0';
int up = 0, sum;        //up储存进位
char c;
int i = 0;
for (; i < strlen(a); i++) {   //使用字符串模拟大数加法
sum = a[i] - '0' + b[i] - '0' + up;
up = sum / key;
sum %= key;
c[i] = char(sum + '0');
c[i + 1] = '\0';
}
if (up > 0) {
c[i] = up + '0';
c[i + 1] = '\0';
}
return c;
}
char *pow2(char a[],int key) {
char b;
memset(b, '0', sizeof(b));
int up=0;
char tmp;
int len = strlen(a);
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
tmp = b[i+j];
b[i + j] = (tmp- '0' + (a[i] - '0')*(a[j] - '0') + up) % key+'0';
up = (tmp - '0' + (a[i] - '0')*(a[i] - '0') + up) / key;
}
}
b[len * 2 - 1] = '\0';
if (up > 0) {
b[len * 2 - 1] = up + '0';
b[len * 2 ] = '\0';
}
return b;
}
int judge(char a[], char b[]) {
for (int i = 0; i < strlen(a); i++) {
if (a[i] != b[i])
return 0;
}
return 1;
}
int main() {
char a;
int len=0, key = 0;
memset(a, '0', sizeof(a));
a[len] = '\0';
if (len > 1)
a[len - 1] = '1';
char t = "1";
for (int i = 0; i <pow(key,len); i++) {
if (judge(a, pow2(a,key))==1) {
printf("%s", a);
}