九倍平方数

思路

拿到这道题先想想，一个数能被 9 整除有什么等价条件？没错，就是各位数字之和能被 9 整除。

题目允许我们把某一位数字 （）替换成 。那每个数字替换后会变成什么？

  • ，：替不替都一样
  • ：数字和多了 2
  • ：数字和多了 6（等价于 mod 9 减了 3）
  • ：不能操作，只能保持原样

所以问题转化成：设原始数字和为 ，有 个 2 和 个 3，每个 2 可以选择给总和加 2，每个 3 可以选择给总和加 6。问是否存在 ， 使得：

$$

关键优化

最多只有 9 种取值（ 就能覆盖所有可能）， 同理。所以不管 、 多大，只需要枚举到 和 就够了。

算法流程：

  1. 遍历字符串统计数字和 、、
  2. 计算目标
  3. 枚举所有可能的 ，存进集合
  4. 枚举所有可能的 ，检查 是否在集合中

最多 次检查，每组数据 扫一遍字符串就行。

代码

#include <bits/stdc++.h>
using namespace std;

char s[1000001];

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%s", s);
        int n = strlen(s);
        int base_sum = 0, cnt2 = 0, cnt3 = 0;
        for(int i = 0; i < n; i++){
            int d = s[i] - '0';
            base_sum += d;
            if(d == 2) cnt2++;
            else if(d == 3) cnt3++;
        }
        int target = (9 - base_sum % 9) % 9;

        // 2*a mod 9 的所有可达值
        bool reach[9] = {};
        for(int a = 0; a <= min(cnt2, 8); a++)
            reach[(2*a) % 9] = true;

        bool found = false;
        for(int b = 0; b <= min(cnt3, 8); b++){
            int need = (target - (6*b) % 9 + 9) % 9;
            if(reach[need]){
                found = true;
                break;
            }
        }
        puts(found ? "YES" : "NO");
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            String s = br.readLine().trim();
            int baseSum = 0, cnt2 = 0, cnt3 = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                baseSum += d;
                if (d == 2) cnt2++;
                else if (d == 3) cnt3++;
            }
            int target = (9 - baseSum % 9) % 9;

            // 2*a mod 9 的所有可达值
            Set<Integer> reach = new HashSet<>();
            for (int a = 0; a <= Math.min(cnt2, 8); a++)
                reach.add((2 * a) % 9);

            boolean found = false;
            for (int b = 0; b <= Math.min(cnt3, 8); b++) {
                int need = (target - (6 * b) % 9 + 9) % 9;
                if (reach.contains(need)) {
                    found = true;
                    break;
                }
            }
            sb.append(found ? "YES" : "NO").append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    s = input().strip()
    base_sum = 0
    cnt2 = 0
    cnt3 = 0
    for ch in s:
        d = int(ch)
        base_sum += d
        if d == 2:
            cnt2 += 1
        elif d == 3:
            cnt3 += 1
    target = (9 - base_sum % 9) % 9
    reach = set()
    for a in range(min(cnt2, 8) + 1):
        reach.add((2 * a) % 9)
    found = False
    for b in range(min(cnt3, 8) + 1):
        need = (target - (6 * b) % 9 + 9) % 9
        if need in reach:
            found = True
            break
    out.append("YES" if found else "NO")
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < t; i++) {
        const s = lines[idx++].trim();
        let baseSum = 0, cnt2 = 0, cnt3 = 0;
        for (let j = 0; j < s.length; j++) {
            const d = s.charCodeAt(j) - 48;
            baseSum += d;
            if (d === 2) cnt2++;
            else if (d === 3) cnt3++;
        }
        const target = (9 - baseSum % 9) % 9;
        const reach = new Set();
        for (let a = 0; a <= Math.min(cnt2, 8); a++) {
            reach.add((2 * a) % 9);
        }
        let found = false;
        for (let b = 0; b <= Math.min(cnt3, 8); b++) {
            const need = (target - (6 * b) % 9 + 9) % 9;
            if (reach.has(need)) {
                found = true;
                break;
            }
        }
        out.push(found ? "YES" : "NO");
    }
    console.log(out.join('\n'));
});

复杂度

  • 时间复杂度：，其中 是所有字符串总长度。每个字符只扫一遍，mod 9 的枚举是常数。
  • 空间复杂度：，存储输入字符串。

总结

这题的核心就两点：一是想到"被 9 整除等价于数字和被 9 整除"，二是发现只有 2 和 3 会产生变化，而 mod 9 的周期性让我们只需要枚举极少的情况。看起来是暴力枚举的分类，但本质上是个数论 + 模运算的小技巧题。