1091. N-自守数.md

【PAT B-1091】N-自守数

题意概述

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

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

输入输出格式

输入在第一行中给出正整数 M，随后一行给出 M 个待检测的、不超过 1000 的正整数。

对每个需要检测的数字，如果它是 N-自守数就在一行中输出最小的 N 和$NK^2$的值，以一个空格隔开；否则输出No。

数据规模

$$N<10,M\le20$$

算法设计

由于要比较 NK^2 的末尾几位与 K 的大小关系，我们可以对$NK^2$进行求余运算。假设 K 有 i 位数，则将$NK^2$对${10}^i$求余的结果与 K 进行比较，看是否相等即可得出结果。关键如何确定 m 是多少呢？我们可以额外设置一个变量 m，初始化为 1。定义一个循环，循环中让 K 每次除以 10 并向下取整，同时令 m 每次乘 10。当 K 的值变成 0 时，有$m={10}^i$。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg mi, ki;
    cin >> mi;
    while (mi--) {
        cin >> ki;
        gg m = 1;
        for (gg i = ki; i != 0; i /= 10)
            m *= 10;
        for (gg n = 1; n < 10; ++n) {
            if (n * ki * ki % m == ki) {
                cout << n << ' ' << n * ki * ki << '\n';
                goto loop;
            }
        }
        cout << "No\n";
    loop:;
    }
    return 0;
}