题解 | 九倍平方数

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

// 1.关于这里为什么对2的个数限制在8个，3的个数限制在2个。
// 1.数的增量只能由2和3来，2的增量是4-2=2，3的增量是3*3-3=6.
// 2.我们要求的是 原来的数的和加上增量后可以被9整除 ( sum%9+(2*j+6*i) )%9==0
// 3.由于sum%9属于0-8范围内，因此 (2*j+6*i)%9 也应该在0-8范围内

// 余数 最小达到增量
// 1    10=2*5
// 2    2=2*1
// 3    12=2*6 or 12=6*2
// 4    4=2*2
// 5    14=2*7
// 6    6=2*3 or 6=6*1
// 7    16=2*8
// 8    8=2*4
// 由上表可以看出，2最大得有8个，6最大得有2个。

// 本题判断 9-sum%9==(2*j+6*i)%9即可


bool ist(string s) {
    int k = s.size();
    int sum = 0, n1 = 0, n2 = 0;
    for (int i = 0; i < k; i++) {
        sum += s[i] - '0';
        sum = sum % 9;
        if (s[i] == '2') n1++;
        if (s[i] == '3') n2++;
    }

    if (sum != 0) {
        int origin = 9 - sum;
        for (int i = 0; i <= min(n2, 2); i++) {
            for (int j = 0; j <= min(n1, 8); j++) {
                if (origin == (j * 2 + i * 6) % 9) {
                    return true;
                }

            }
        }
    } else {
        return true;
    }

    return false;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        if (ist(s)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }

    }
}