题解 | 九倍平方数

我们知道每一位数加起来是9的倍数的可以被9整除，diffNine代表了所有位加起来还差多少能被9整除，比如diffNine算得2，问题变成了需要多少2（由2->4位和增加2），6（由3->9位和增加6）组合得到2+9n。通过遍历得到2，3的个数，设为m,n。即： 2m+6n=diff+9k , k为自然数 =====> (2m+6n)%9 = diff。遍历找到是否有合适的组合即可。

#include <iostream>
using namespace std;

int diffNine(string num, int& twoNum, int& threeNum) {
    int sum = 0;
    for (auto c : num) {
        if (c == '2')twoNum++;
        if (c == '3')threeNum++;
        sum += c - '0';
    }
    return 9 - sum % 9;
}

int main() {
    int t;
    cin >> t;
    while (t--) { // 注意 while 处理多个 case
        string s;
        cin >> s;
        int threeNum = 0, twoNum = 0;
        int diff = diffNine(s, twoNum, threeNum);
        if (diff == 9) {
            cout << "YES" << endl;
            continue;
        }
        int flag = 1;
        // cout << twoNum << ' ' << threeNum << endl;
        for (int i = 0; i <= twoNum && flag; ++i) {
            for (int j = 0; j <= threeNum && flag; ++j) {
                int temp = 2 * i + 6 * j;
                if (temp % 9 == diff) {
                    cout << "YES" << endl;
                    flag = 0;
                }
            }
        }
        if (flag)cout << "NO" << endl;
    }
    return 0;
}