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)；

求解代码

importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.io.OutputStreamWriter;importjava.io.PrintWriter;importjava.util.StringTokenizer;publicclassMain{publicstaticbooleanisGoodNum(Strings){longsum=0;intcount2=0;intcount3=0;for(charc:s.toCharArray()){intnum=c-'0';sum+=num;if(num==2){count2++;}elseif(num==3){count3++;}}intrest=(int)(sum%9);if(rest==0){returntrue;}inttarget=(9-rest)%9;for(inti=0;i<=Math.min(count2,8);i++){for(intj=0;j<=Math.min(count3,2);j++){if((i*2+j*6)%9==target){returntrue;}}}returnfalse;}publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringTokenizerin=newStringTokenizer(br.readLine());PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));intt=Integer.parseInt(in.nextToken());for(inti=0;i<t;i++){in=newStringTokenizer(br.readLine());Strings=in.nextToken();if(isGoodNum(s)){out.println("YES");}else{out.println("NO");}}out.flush();out.close();br.close();}}