B1091 N-自守数 （15分）

如果某个数 \(K\)的平方乘以\(N\) 以后，结果的末尾几位数等于 \(K\)，那么就称这个数为“\(N\)-自守数”。例如 \(3×92
​^2
​=25392\)，而 25392 的末尾两位正好是 92，所以 92 是一个 3-自守数。

本题就请你编写程序判断一个给定的数字是否关于某个 N 是 N-自守数。

输入格式：

输入在第一行中给出正整数 \(M（≤20）\)，随后一行给出 \(M\) 个待检测的、不超过 1000 的正整数。

输出格式：

对每个需要检测的数字，如果它是 \(N\)-自守数就在一行中输出最小的 $N $和 \(NK
​^2\)

的值，以一个空格隔开；否则输出 No。注意题目保证 \(N<10\)。

输入样例：

3

92 5 233

输出样例：

3 25392

1 25

No

思路

对0-9逐一检验

9000000

为什么我的代码有一个测试点过不去。

因为对0所有数都会自守的，对一些特殊的数要特别看待。

#include<bits/stdc++.h>

using namespace std;

int tmp_ans[9];

int ans[9];

int change(int a[],int b){

	int num = 0;

 	while(b!=0){

        a[num++]=b%10;

        b/=10;

    }

 	return num;

}

int main(void){

	int m,tmp,tmp_num,num,true_ans;

	int flag;

	scanf("%d",&m);

	getchar();

	for(int i=0;i<m;i++){//对每个数都处理一次标记

		flag = -1;

		scanf("%d", &tmp);//要判断有几位数，最大是4位

		tmp_num=change(tmp_ans,tmp);

		for(int j=0;j<10;j++){

			flag = -1;

			true_ans=tmp*tmp*j;

			num=change(ans,true_ans);

			for(int k=0;k<tmp_num;k++){

				if(ans[k]!=tmp_ans[k]){

					flag = k;

					break;

				}

			}

			if(flag==-1){

				printf("%d %d\n",j,true_ans);

				break;

			}

		}

		if(flag!=-1)

			printf("No\n");/*无自守数*/

	}

	return 0;

}

AC代码

/*消去0这个自守。*/

for(int j=1;j<10;j++)

来自别人的AC代码

不是暴力而是数学的写法。

以题中\(3×92^2=25392\)为例，当数\(Ｋ\)为\(92\)，自守数\(Ｎ\)为\(３\)时，有

(3×92×92-92)% 100 = 0

推广即得

(NKK-K) % ( 10 ^ {length( K ) } ) = 0

#include<stdio.h>

int len(int K);    //该函数返回10的Ｋ的长度次方。

int main()

{

    int M, K, l, flag;

    scanf("%d", &M);

    for(int i = 0; i < M; i++){

        scanf("%d", &K);

        l = len(K);

        flag = 0;    // flag标记Ｋ是否有自守数

        for(int j = 0; j < 10; j++){

            if((j * K * K - K) % l == 0){

                printf("%d %d\n", j, j*K*K);

                flag = 1;

                break;　　//得到最小自守数后直接break

            }

        }

        if(flag == 0)    printf("No\n");

    }

    return 0;

}

int len(int K){

    int len = 1;

    while(K){

        len *= 10;

        K /= 10;

    }

    return len;

}