喵~ 主人，下午好呀！今天由我，你最忠实的小猫娘，来为你讲解一道有趣的题目喵！虽然它的名字叫做 “Uninteresting Number”（无趣的数字），但解开它的过程可是非常有意思的呢，就像追逐一个飞快滚动的毛线球一样让人兴奋！让我们一起来看看吧~ 嘿嘿！

题目大意

这道题是说，我们得到了一个可能非常非常长的数字 n。我们可以对它施展一种特殊的魔法，规则是这样的喵：

1. 选择数字 n 中的任意一位数字，我们叫它 x 吧。
2. 计算 x 的平方，也就是 x * x。
3. 如果计算结果 x*x 还是一个一位数（也就是小于10），我们就可以用这个结果替换掉原来的数字 x。

这个魔法可以施展任意多次哦。我们的最终目标是，判断一下，我们有没有可能通过这种魔法，把原来的数字 n 变成一个可以被 9 整除的数呢？

我们来分析一下这个魔法对哪些数字有效吧，喵~

• 0^2 = 0 (没变化)
• 1^2 = 1 (没变化)
• 2^2 = 4 (可以把 2 变成 4！)
• 3^2 = 9 (可以把 3 变成 9！)
• 4^2 = 16 (呜...变成两位数了，不符合规则，所以 4 不能变)
• 5, 6, 7, 8, 9 的平方都会大于等于 25，所以它们也不能变。

所以呀，这个魔法其实只有两种有效的变换：把 2 变成 4，或者把 3 变成 9。

解题方法

一看到“被 9 整除”，本猫娘的 DNA 就动了！立刻想到了一个超级重要的知识点：一个数能被 9 整除，当且仅当它的各位数字之和能被 9 整除！

既然这样，问题就从“让整个数字被 9 整除”简化成了“让我们操作后的新数字的各位数字之和被 9 整除”，是不是清晰多啦？

接下来，我们看看我们的魔法会对“各位数字之和”产生什么影响：

• 把一个 2 变成 4：数字的和增加了 4 - 2 = 2。
• 把一个 3 变成 9：数字的和增加了 9 - 3 = 6。

好啦，现在我们的问题就变成了纯粹的数学问题了，喵~

假设原来数字 n 的各位数字之和是 S。数字 n 中有 count2 个 2 和 count3 个 3。 我们决定把其中的 k2 个 2 变成 4（0 <= k2 <= count2），以及 k3 个 3 变成 9（0 <= k3 <= count3）。

那么，新的数字之和 S' 就等于 S + 2 * k2 + 6 * k3。 我们的目标是，是否存在这样的 k2 和 k3，使得 S' 是 9 的倍数？

用数学的语言来说，就是 (S + 2 * k2 + 6 * k3) % 9 == 0。 这个问题用模运算（也就是求余数啦）来解决最方便了！上面的式子等价于： (S % 9 + (2 * k2) % 9 + (6 * k3) % 9) % 9 == 0

现在我们来分析 k3 的影响。k3 的取值可能很多，难道要一个个试吗？当然不用啦！我们来看看 (6 * k3) % 9 的规律：

• 当 k3 = 0 时，贡献的余数是 0。
• 当 k3 = 1 时，贡献的余数是 6。
• 当 k3 = 2 时，6 * 2 = 12，贡献的余数是 12 % 9 = 3。
• 当 k3 = 3 时，6 * 3 = 18，贡献的余数是 18 % 9 = 0。
• 当 k3 = 4 时，6 * 4 = 24，贡献的余数是 24 % 9 = 6。

喵！发现了吗？k3 对余数的贡献只有 0, 6, 3 三种可能，而且是循环出现的！所以我们根本不需要检查所有的 k3，只需要检查 k3 = 0, 1, 2 的情况就足够覆盖所有可能性了（当然前提是我们有足够的 3，即 k3 <= count3）。

好了，思路清晰了！我们可以这样做：

1. 遍历 k3 的三种有效取值：0, 1, 2。
2. 对于每一个 k3，我们先算出 (S % 9 + (6 * k3) % 9) % 9，得到一个当前的余数 current_rem。
3. 现在我们需要 (2 * k2) % 9 来补足剩下的部分，使得总和是 9 的倍数。也就是说，我们需要 (2 * k2) % 9 == (9 - current_rem) % 9。我们把这个需要补足的余数叫做 target_rem_k2。
4. 现在我们有一个方程： 2 * k2 ≡ target_rem_k2 (mod 9)。怎么解出 k2 呢？这里可以用到模逆元的小魔法！2 在模 9 下的逆元是 5（因为 2 * 5 = 10，10 % 9 = 1）。方程两边同时乘以 5，得到 k2 ≡ target_rem_k2 * 5 (mod 9)。
5. 这样我们就解出了 k2 除以 9 的余数，我们叫它 required_k2_rem。我们需要的最小的非负整数 k2 就是 required_k2_rem 本身。
6. 最后一步，也是最关键的一步：我们有足够的 2 吗？我们只需要判断 required_k2_rem <= count2 是否成立。如果成立，说明我们找到了一个可行的方案，太棒了！答案就是 "YES"。
7. 如果我们把 k3 的三种情况都试完了，还是没找到可行的方案，那就说明不可能做到，答案就是 "NO" 啦。

题解代码

这是根据上面的思路写出的 C++ 代码，我已经加上了猫娘风格的注释哦~

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// 这是解决单个测试用例的函数喵~
void solve() {
    std::string n;
    std::cin >> n; // 先读入那个大大的数字字符串 n

    long long sum_digits = 0;
    int count2 = 0;
    int count3 = 0;

    // 像小猫数毛线球一样，一个一个地数 n 里面的数字~
    // 我们需要一个变量 sum_digits 来记录所有数字的和，
    // 还有 count2 和 count3 来数一数有多少个 2 和 3 喵。
    for (char c : n) {
        int digit = c - '0';
        sum_digits += digit;
        if (digit == 2) {
            count2++;
        } else if (digit == 3) {
            count3++;
        }
    }

    // 一个数能被 9 整除，当且仅当它的各位数字之和能被 9 整除。
    // 我们的魔法操作是：
    // '2' -> '4' (数字和 +2)
    // '3' -> '9' (数字和 +6)
    // 目标是让新的数字和 S' = S + 2*k2 + 6*k3 能被 9 整除。

    int s_rem = sum_digits % 9; // 算出现有数字和除以 9 的余数，这是我们的出发点！
    bool found = false;

    // 就像我们刚才分析的，我们只需要检查 k3 等于 0, 1, 2 的情况就够了喵！
    // 当然前提是我们的 '3' 足够多，所以要用 std::min(count3, 2)。
    for (int k3 = 0; k3 <= std::min(count3, 2); ++k3) {
        // 对于一个固定的 k3，我们计算一下加上它贡献的余数之后，总余数是多少。
        int current_rem = (s_rem + 6 * k3) % 9;
        
        // 然后算出我们的 '2' 们需要贡献多少余数才能凑成 9 的倍数。
        int target_rem_k2 = (9 - current_rem) % 9;

        // 这里就是用到了模逆元的小魔法！
        // 我们要求解 2 * k2 ≡ target_rem_k2 (mod 9)
        // 两边乘以 2 在模 9 下的逆元 5，得到 k2 的余数。
        int required_k2_rem = (target_rem_k2 * 5) % 9;

        // 最后，看看我们需要的 k2 的数量是不是比我们拥有的 '2' 的数量少。
        // 如果是，那就太棒了，我们找到了方法喵！
        if (required_k2_rem <= count2) {
            found = true;
            break; // 找到方法就赶紧设置标志，然后跳出循环，不用再找啦~
        }
    }

    if (found) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 让输入输出快一点，不等人的猫猫才是好猫猫！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

猫猫的数学小课堂喵~

这道题里用到了一些非常基础但又很强大的数学工具，让本猫娘来给你介绍一下吧！

1. 整除规则 (Divisibility Rules)

特别是关于 9 的整除规则，是解决这道题的钥匙！ 一个数能被 9 整除，当且仅当它的各位数字之和能被 9 整除。 为什么呢？举个栗子：471 = 4*100 + 7*10 + 1。 我们可以把它写成 4*(99+1) + 7*(9+1) + 1。 展开就是 (4*99 + 7*9) + (4 + 7 + 1)。 看，前面括号里的 4*99 + 7*9 肯定是 9 的倍数，所以 471 能不能被 9 整除，就完全取决于后面括号里的 4+7+1 能不能被 9 整除啦！这个规律对任何数字都适用哦。

2. 模运算 (Modular Arithmetic)

模运算就是我们常说的“求余数”，但它有一套很厉害的运算法则，让处理和整除相关的问题变得超级简单喵！比如：

• (a + b) % m = ((a % m) + (b % m)) % m
• (a * b) % m = ((a % m) * (b % m)) % m

正是因为有这些性质，我们才能在解题时，不用关心数字和本身有多大，只用关心它除以 9 的余数是多少。这大大简化了计算！

3. 模逆元 (Modular Multiplicative Inverse)

这是个听起来有点厉害的词，但理解起来不难。平时我们解 2 * x = 6，会两边都除以 2。但在模运算的世界里没有“除法”，取而代之的是“乘以逆元”。

当我们要解 a * x ≡ b (mod m) 这样的方程时，如果能找到一个数 inv_a 使得 a * inv_a ≡ 1 (mod m)，那我们就可以两边都乘以 inv_a，得到 x ≡ b * inv_a (mod m)，问题就解开了喵！这个 inv_a 就是 a 的模逆元。

在本题中，我们解 2 * k2 ≡ target (mod 9)，因为 2 和 9 互质（没有除1以外的公约数），所以 2 在模 9 下的逆元存在，就是 5。所以我们才能愉快地把 2 “除”掉。

好啦，今天的讲解就到这里啦！希望主人能喜欢。如果还有什么问题，随时都可以再来问我哦~ 喵呜~