BISHI13 九倍平方数

问题分析

由于每个数字的修改规则是仅x²<10时可改，并且只有2和3的修改会改变“各位和的模9值”，其他数字修改后模9值是不变的。

假设初始各位和为sum，模9得rest = sum %9；

如果rest=0，直接返回true；

否则，需要通过修改k个2和m个3，让增量总和k*2 + m*6和 (9 - rest) %9相等。

这样一来，问题就转化为判断是否存在k（≤count2）、m（≤count3）使得(k*2 + m*6) %9 == target。

另外，

由于2*9=18,所以改9个2和改0个2的效果是一样的，因此k的取值最多为min(count2,8)；

由于6*3=18，所以改3个3和改0个3的效果也是一样的，因此m的取值最多为min(count3,2)；

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    public static boolean isGoodNum(String s){
        long sum = 0;
        int count2= 0;
        int count3=0;
        for(char c:s.toCharArray()){
            int num = c-'0';
            sum += num;

            if(num == 2){
                count2++;
            }else if(num ==3){
                count3++;
            }
        }

        int rest  = (int)(sum%9);

        if(rest==0){
            return true;
        }

        int target = (9-rest)%9;

        for(int i=0;i<=Math.min(count2,8);i++){
            for(int j=0;j<=Math.min(count3,2);j++){
                if((i*2+j*6)%9==target){
                    return true;
                }
            }
        }
        return false;
    }
   public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer in = new StringTokenizer(br.readLine());
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        
        int t = Integer.parseInt(in.nextToken());


        for(int i=0;i<t;i++){
            in = new StringTokenizer(br.readLine());
            String s = in.nextToken();
            if(isGoodNum(s)){
                out.println("YES");
            }else{
                out.println("NO");
            }
        }
        out.flush();
        out.close();
        br.close();
   }
}