题解 | 九倍平方数

重要数学知识：能被9整除，在于各位数之和为9的倍数，即summ % 9 = 0，

如果有余数，那么余数就是差的部分。

0 1 没必要； 2 3 能平方； 4-9 都不行；一个2贡献2的增量，一个3贡献6的增量

因此我们要统计整个字符串里2和3出现的次数cnt_2,cnt_3，

然后以2和3的次数为上限进行双重for循环，找到一个序列（i，j）补齐余数。

值得优化的是：2最大只需要遍历到第八个即可（ (增量2*9=18) %9 = 0),第九个以后进入轮回，

3最大遍历到第2个（ (增量6*3 = 18) %9 = 0 ），第三个以后进入轮回。

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        string n;
        cin >> n;//1234567890
        int cnt_2 = 0, cnt_3 = 0;
        long long summ = 0;
        for(char x: n){
            if (x == '2') {
                cnt_2++;//1
            }
            else if (x == '3') {
                cnt_3++;//1
            }
            summ += x-'0';
        }
        int yu = summ % 9;//计算距离9已经走了多少
        if (yu == 0) {//余数为0直接就是9的倍数了
            cout << "YES" << '\n';
            continue;
        }
        int need_to_add = (9 - yu) % 9; //计算距离9还差多少
        int flag = 0;//为1说明经过调整后可以变成9的倍数
        for (int i = 0; i <= min(cnt_2, 8); i++) {
            for (int j = 0; j <= min(cnt_3, 2); j++) {
                if ((i*2 + j*6) % 9 == need_to_add) {//记得加和取模9
                    flag = 1;// 找到了满足序列
                    break;
                }
            }
        }
        if (!flag) {
            cout << "NO" << '\n';
        }
        else {
            cout << "YES" << '\n';
        }
    }
}