题解 | 九倍平方数

#include <iostream>
using namespace std;
bool isGoodNum(const string& s){
    int sum=0;
    int cnt2=0;
    int cnt3=0;
    for(char c:s){
        int digit=c-'0';
        sum+=digit;
        if(digit==2) cnt2++;
        else if(digit==3) cnt3++;
    }
    int R_init=sum%9;
    if(R_init==0) return true;
    int target_delta=(9-R_init)%9;
    for(int i=0;i<=min(cnt2,8);i++){
        for(int j=0;j<=min(cnt3,2);j++){
            if(target_delta==(i*2+j*6)%9) return true;
        }
    }
    return false;
}
int main() {
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        if(isGoodNum(s)){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")