兩題都是自守數問題。
第一題是簡單的十進制的自守數判斷：
以376為例
376 被乘數
X 376 乘數
----------
2256 第一個部分積=被乘數*乘數的倒數第一位
2632 第二個部分積=被乘數*乘數的倒數第二位
1128 第三個部分積=被乘數*乘數的倒數第三位
----------
141376 積
本問題所關心的是積的最後三位。分析產生積的後三位的過程，可以看出，在每一次的部分積中，並不是它的每一位都會對積的後三位產生影響。總結規律可以得到：在三位數乘法中，對積的後三位產生影響的部分積分別為：
第一個部分積中：被乘數最後三位*乘數的倒數第一位
第二個部分積中：被乘數最後二位*乘數的倒數第二位
第三個部分積中：被乘數最後一位*乘數的倒數第三位
將以上的部分積的後三位求和後截取後三位就是三位數乘積的後三位。這樣的規律可以推廣到同樣問題的不同位數乘積。
代碼：
[cpp]
#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>
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;
}
第二題要處理N進制K位的自守數求解問題。
對所有情況從低位到高位搜索遍歷即可。
[cpp]
#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;
}
#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;
}
