题解 | 九倍平方数

#include <iostream>
#include <string>
using namespace std;

bool isGood(string s) {
    int count2 = 0, count3 = 0;
    int sum = 0;
    
    for (char c : s) {
        int digit = c - '0';
        sum += digit;
        if (digit == 2) count2++;
        if (digit == 3) count3++;
    }
    
    // 如果已经能被9整除
    if (sum % 9 == 0) return true;
    
    // 枚举所有可能的a和b
    // 限制枚举范围，但要注意count2和count3可能为0
    for (int a = 0; a <= min(count2, 8); a++) {
        for (int b = 0; b <= min(count3, 2); b++) {
            if ((sum + 2*a + 6*b) % 9 == 0) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << (isGood(s) ? "YES" : "NO") << endl;
    }
    return 0;
}

这道题的核心解法是：由于只有数字2可以变成4（和增加2），数字3可以变成9（和增加6），其他数字操作后不变或无法操作，因此问题转化为判断能否通过选择一定数量的2和3进行变换，使得最终所有数位之和能被9整除。具体做法是：先计算原始数位和sum，统计2的个数count2和3的个数count3，然后枚举a个2被变换（0≤a≤min(count2,8)）和b个3被变换（0≤b≤min(count3,8)），检查是否存在(sum + 2a + 6b) % 9 == 0的情况。

最大的坑点在于题目中“长度≤10^5”指的是数字串的位数可达10万位，而不是数值大小小于10^5，这意味着输入数字远超任何整数类型的存储范围，必须用字符串读入和处理，绝不能使用int或long long，否则会导致溢出和错误结果。我之前做题不看题，一直以为数值大小小于10^5，我说小菜一碟啊！结果是看花了眼。