题解 | 九倍平方数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//判断字符串经过平方操作是否为好数，只能替换字符串中的2和3
//解题关键：各位上的数之和能被9整除则数yes
bool solve(){
    string s;
    cin>> s;
    int n = s.size();
    //看原数能否被整除，统计2和3的数量，一个多加了2， 一个加了6
    ll sum = 0;
    int cnt2 =0, cnt3 = 0;
    for (int i = 0;  i < n; i++){
        int temp = s[i] -'0';
        sum += temp;
        if(temp == 2) cnt2++;
        if(temp == 3) cnt3++;
    }
    if(sum % 9 == 0) return 1; 
    //无操作返回0
    if(cnt2 == 0 && cnt3 == 0) return 0;
    for(int i = 0; i<= cnt2; i++) {
        ll temp1 = sum;
        for(int j = 0;j <= cnt3; j++){
            if((sum+ i*2+ j*6)% 9 == 0)
                return true;
        }
    }
    return false;
    
}
int main() {
    int t;
    cin >> t;
    while(t--){
       if( solve()){
        cout << "YES\n";
       }else cout << "NO\n";
    }
    return 0;
}
// 64 位输出请用 printf("%lld")