题解 | 九倍平方数

using System;
using System.Collections.Generic;
public class Program {
    public static void Main() {
        //有一个能被9整除的数的特性：它的各位数字之和也能被9整除
        //因此我们可以通过替换每一位上小于3的数字为其，且每当把一个2变成4, 3变成9时，数字各位之和会增加2或6，从而改变数字各位之和对9的模值
        int.TryParse(Console.ReadLine(), out int n);

        for (int i = 0; i < n; i++)
        {
            bool candBeDividedBy9 = false;
            string input = Console.ReadLine();
            int countOf2 = 0;
            int countOf3 = 0;

            char[] digits = input.ToCharArray();
            int sumOfDigits = 0;
            foreach (var ch in digits)
            {
                sumOfDigits += (ch - '0');
                if (ch == '2')
                {
                    countOf2++;
                }
                else if (ch == '3')
                {
                    countOf3++;
                }
            }

            int remainder = sumOfDigits % 9;
            

            if (remainder == 0)
            {
                candBeDividedBy9 = true;
            }
            else
            {   
            //增量只能由2和6提供，remiander加上增量后能够被9整除就说明是好数，即(sumOfDigits%9 + (countOf2*2 + countOf3*6)%9 ==0
                for (int j = 0; j <= countOf2; j++)
                {
                    for (int k = 0; k <= countOf3; k++)
                    {
                        int increment = j * 2 + k * 6;
                        if ((remainder + increment) % 9 == 0)
                        {
                            candBeDividedBy9 = true;
                            break;
                        }
                    }
                    if (candBeDividedBy9)
                    {
                        break;
                    }
                }
                

            }
            Console.WriteLine(candBeDividedBy9 ? "YES" : "NO");
        }
    }
}