C. Uninteresting Number（无趣的数字）

题目核心分析

关键知识点

一个数能被 $9$ 整除的充要条件：它的各位数字之和能被 $9$ 整除。

操作规则解析

题目允许我们将一个数字 $x$ 替换为 $x^2$，仅当 $x^2 < 10$，符合条件的数字只有：

• $0$：$0^2=0$，差值 $0$
• $1$：$1^2=1$，差值 $0$
• $2$：$2^2=4$，差值 $+2$
• $3$：$3^2=9$，差值 $+6$

其他数字（$4\sim9$）都无法进行任何操作！

解题思路

1. 计算原数字的各位和 $sum$，同时统计字符串中 $2$ 的数量 $cnt2$、$3$ 的数量 $cnt3$；
2. 如果 $sum \% 9 = 0$，直接输出 YES；
3. 否则，我们需要通过操作若干个 $2$ 和 $3$，让总和增加 $k$，满足 $(sum + k) \%9 =0$；
4. 每个 $2$ 能贡献 $+2$，每个 $3$ 能贡献 $+6$，我们只需要判断：是否存在 $i \le cnt2$、$j \le cnt3$，使得 $(2i + 6j) \%9 = (9 - sum\%9)$。

完整代码（带注释）

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入输出，应对大数据
    
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        long long sum = 0; // 数字各位和
        int cnt2 = 0, cnt3 = 0; // 统计2和3的数量
        
        for(int i = 0; i < s.size(); i++)
        {
            sum += s[i] - '0';
            if(s[i] == '2') cnt2++;
            if(s[i] == '3') cnt3++;
        }
        
        // 原本就满足条件，直接输出YES
        if(sum % 9 == 0)
        {
            cout << "YES\n";
            continue;
        }
        
        // 需要补充的差值（模9意义下）
        int need = 9 - sum % 9;
        bool ok = false;
        
        // 枚举使用多少个2和3
        for(int i = 0; i <= cnt2; i++)
        {
            for(int j = 0; j <= cnt3; j++)
            {
                // 2*i + 6*i 是总增量，模9等于需要的差值即可
                if((2 * i + 6 * j) % 9 == need)
                {
                    ok = true;
                    break;
                }
            }
            if(ok) break;
        }
        
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

代码细节讲解

1. 输入优化 ios::sync_with_stdio(false); cin.tie(nullptr); 用于加速大数据输入输出，避免超时（题目数字长度可达 $10^5$）。

2. 统计核心数据 遍历字符串，计算数字和，同时统计可操作的 $2$ 和 $3$ 的数量。

3. 判断条件 双重循环枚举使用的 $2$ 和 $3$ 的数量，检查总增量模 $9$ 是否等于需要补充的值。

   • 每个 $2$ 贡献 $+2$
   • 每个 $3$ 贡献 $+6$

4. 输出结果 找到符合条件的组合输出 YES，否则输出 NO。

时间复杂度

• 单次测试用例：$O(cnt2 \times cnt3)$
• 由于 $cnt2、cnt3$ 最大为 $9$（模 $9$ 下循环 $0\sim8$ 即可），实际复杂度近似 $O(1)$
• 整体完全满足题目 $10^5$ 长度的限制。

总结

1. 本题核心是9的整除特性 + 有限的可操作数字；
2. 只有 $2$、$3$ 能改变数字和，增量固定；
3. 枚举少量组合即可判断答案，代码简洁高效。