2014
02-17

# Self-Replicating Numbers

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.

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).

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).

2 1
10 4

2
0
1
1
9376

376 被乘数
X 376 乘数
———-
2256 第一个部分积=被乘数*乘数的倒数第一位
2632 第二个部分积=被乘数*乘数的倒数第二位
1128 第三个部分积=被乘数*乘数的倒数第三位
———-
141376 积

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

int main()
{
/*#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif*/
int n;
while(scanf(" %d",&n)!=EOF)
{
//数的位数
int k = 1;
if(n == 0 || n == 1)
{
printf("NO\n");
continue;
}
int temp = n;
while(temp/10!=0)
{
temp /= 10;
k *= 10;
}
//求余的系数
int kk = k*10;
k = kk;
int part = 0;
int mul = 10;
while(k>=10)
{
//被乘数
int a = n%k;
//乘数
int b = ((n - (n/mul)*mul)/(mul/10))*(mul/10);
//部分积
part += (a*b)%kk;
part %=kk;
k /=10;
mul *=10;
}
if(n == part)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

struct Node
{
char self[2005];
};
Node p[1000];
int a[2005];
int m;
int b,n;

char Change(int x)
{
if (x<=9)
return '0'+x;
else
return 'A'+x-10;
}
//从低位往高位搜索
void dfs(int dep,int sum)
{
if(dep>n)
{
if(a[n]>0 || n == 1)
{
for(int i=n; i>=1; i--)
{
p[m].self[n-i] = Change(a[i]);
}
p[m].self[n] = '\0';
m++;
}
return;
}
int tol = 0;
for(a[dep]=0; a[dep]<b; a[dep]++)
{
tol = 0;
for(int i=1; i<=dep; i++)
{
int j = dep-i+1;
tol += a[i]*a[j];
}
if((tol+sum)%b == a[dep])
{
dfs(dep+1,(tol+sum)/b);
}
}
}
bool cmp(Node a,Node b)
{
return strcmp(a.self,b.self)<0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while(scanf(" %d %d",&b,&n)!=EOF)
{
m = 0;
dfs(1,0);
sort(p,p+m,cmp);
printf("%d\n",m);
for(int i=0; i<m; i++)
{
printf("%s\n",p[i].self);
}
}
return 0;
}

1. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}