题解 | 九倍平方数

C++ 位数最大1e5所以不能直接除。规律：一个数能被9整除，当且仅当它的各位数字之和能被9整除

#include <array>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 一个数能被9整除，当且仅当它的各位数字之和能被9整除
    // x^2 < 10 即 x=2或3
    // n%9==0 || (n+i*(4-2)+j*(9-3))%9==0
    int t;
    cin >> t;
    while (t--) {
        string a;
        cin >> a;
        vector<int> n;
        for (auto i:a) {
            n.push_back(i-'0');
        }
        // cout << n%9 << endl;
        // 最长可是有10^5位
        int s=0, cnt2=0, cnt3=0;
        for (auto i:n) {
            s += i;
            if (i==2) cnt2++;
            else if (i==3) cnt3++;
        }
        // cout << s << ' ' << cnt2 << ' ' << cnt3 << endl;
        if (s%9==0) cout << "YES" << endl;
        else {
            int f=0;
            for (int i=0; i<=cnt2; i++) {
                for (int j=0; j<=cnt3; j++) {
                    if ((s+2*i+6*j)%9==0) {
                        f=1;
                        break;
                    }
                }
                if (f) break;
            }
            if (f) cout << "YES" << endl;
            else cout << "NO" << endl; 
        }
        
    }
}
// 64 位输出请用 printf("%lld")