NekoNowcoder

Appearance

优美数字 - 题解 ​

标签与难度 ​

标签: 数学, 模拟, 整数反转, 模运算, 基础算法 难度: 900

题目大意喵~ ​

主人你好呀！这道题是小 D 的一个可爱发现，喵~

题目定义了一种叫做“优美数字”的东西。一个数字 x 如果是优美的，需要满足一个条件：x 的平方（也就是 x2x^2）能够被 x 的反转数 rev(x) 整除。

这里的 rev(x) 就是把数字 x 的十进制位反过来写。举个栗子：

  • 如果 x = 84，那么 rev(x) = 48。
  • 如果 x = 198，那么 rev(x) = 891。

我们的任务就是，对于给出的好多个数字，判断它们每一个是不是“优美数字”，然后告诉小 D “Yes” 还是 “No”，呐~

解题思路分析 ​

这个问题其实很直白呢，就像猫猫我追着自己的尾巴转圈圈一样，我们只需要跟着题目的定义一步一步来就好啦！整个过程可以分成两个清晰的小任务，喵~

第一步：怎么得到反转数 rev(x) 呢？ ​

要把一个数字反转过来，我们可以用一个很经典的数学小技巧，就像从一串猫爪印里倒着走回来一样！

我们来拿 x = 198 举个例子吧：

  1. 先准备一个新数字 reversed_num，初始值是 0。
  2. 看看 198 的个位数是多少？是 8 (也就是 198 % 10)。我们把它取下来，加到 reversed_num 里。现在 reversed_num 是 8。然后把 198 的个位去掉，变成 19 (也就是 198 / 10)。
  3. 现在看 19，它的个位数是 9。我们把它取下来，拼到 reversed_num 的后面。怎么拼呢？先把 reversed_num 乘以 10（变成 80），再加上 9，得到 89。然后把 19 的个位去掉，变成 1。
  4. 最后看 1，它的个位数就是 1。我们再把它拼到 reversed_num 后面。先把 reversed_num 乘以 10（变成 890），再加上 1，得到 891。然后把 1 的个位去掉，变成 0。
  5. 当原来的数字变成 0 的时候，我们就大功告成啦！198 的反转数 891 就到手了！

这个过程可以用一个循环来实现，直到我们把原数字的每一位都“榨干”为止，喵~

第二步：判断整除和一些小细节 ​

得到了反转数 rev_x 之后，我们就要判断 x2x^2 能不能被它整除。在编程里，判断整除非常简单，就是用取模运算符 %。如果 A % B == 0，就说明 A 能被 B 整除。

所以，我们的判断条件就是：

(x×x)(modrev(x))==0(x \times x) \pmod{\text{rev}(x)} == 0

一个非常重要的提醒！ 主人要注意哦，题目里的数字 x 可能会有点大（比如接近 10910^9），那它的平方 x2x^2 就会变得非常非常大（可能达到 101810^{18}）！如果用普通的 int 类型来存储，就像想把大大的猫爬架塞进小小的猫窝里，会“溢出”的！所以，为了保证计算结果的准确性，我们必须使用 long long 这种能装下更大数字的数据类型，呐。

总结一下我们的计划：

  1. 写一个函数，用数学方法计算一个 long long 类型数字的反转数。
  2. 在主函数里，循环处理每一个输入的数字 x。
  3. 对每个 x，调用函数得到它的反转数 rev_x。
  4. 计算 (x * x) % rev_x，如果结果是 0，就输出 "Yes"，否则输出 "No"。

这样一来，问题就迎刃而解啦！

代码实现 ​

这是我根据上面的思路，精心为你准备的一份代码，注释超详细的哦，喵~

cpp
#include <iostream>

// 为了提高输入输出效率，让程序跑得更快，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

// 这是一个专门用来反转数字的函数，喵~
// 输入一个 long long 类型的数字 n，返回它的反转数
long long reverse_number(long long n) {
    long long reversed_num = 0;
    long long temp_n = n; // 用一个临时变量来操作，不改变原来的 n

    while (temp_n > 0) {
        // 1. 取出 temp_n 的最后一位
        int digit = temp_n % 10;
        // 2. 将这位数拼接到 reversed_num 的末尾
        reversed_num = reversed_num * 10 + digit;
        // 3. 从 temp_n 中移除最后一位
        temp_n /= 10;
    }
    return reversed_num;
}

int main() {
    // 调用快速 I/O 函数
    fast_io();

    int t; // t 是测试用例的数量
    std::cin >> t;

    while (t--) {
        long long x; // 用 long long 来存储输入的数字，防止溢出
        std::cin >> x;

        // 调用函数计算 x 的反转数
        long long rev_x = reverse_number(x);

        // 题目的核心逻辑：判断 x 的平方是否能被 rev_x 整除
        // 注意：x*x 也需要用 long long 来计算，以防溢出
        if ((x * x) % rev_x == 0) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(T⋅log⁡10(max⁡(x)))O(T \cdot \log_{10}(\max(x))) 对于每个测试用例，我们都需要处理一个数字 x。处理的核心操作是反转数字，reverse_number 函数的循环次数取决于数字 x 的位数。一个正整数 x 的十进制位数大约是 log⁡10(x)\log_{10}(x)。如果有 T 个测试用例，总的时间复杂度就是 O(T⋅log⁡10(x))O(T \cdot \log_{10}(x))。这个速度是非常快的，完全不用担心超时，喵~

  • 空间复杂度: O(1)O(1) 在整个计算过程中，我们只使用了几个变量（如 t, x, rev_x, reversed_num, temp_n）来存储临时的数值。我们没有使用随输入规模增大的数组或者其他数据结构。所以，我们占用的额外空间是固定的，也就是常数级别的，喵~

知识点总结 ​

这道题虽然简单，但也是练习基本功的好机会哦！

  1. 整数反转: 学会了用取模和除法运算来高效地反转一个整数，这是一个非常经典的小算法。
  2. 模运算: 熟练使用取模运算符 % 来判断整除关系，这是数论问题的基础。
  3. 数据类型选择: 深刻理解了在处理可能很大的数字时，选择合适的数据类型（比如 long long）是多么重要，可以避免因为整数溢出导致的错误。
  4. 代码封装: 将特定功能（如反转数字）封装成一个独立的函数，会让主程序逻辑更清晰，代码也更易于阅读和维护，是个好习惯的说！

希望这篇题解能帮到你，主人！如果还有其他问题，随时可以来找我玩，喵~