BISHI13　九倍平方数¶

简单通过率 42.98%python3样例通过牛客 AC

牛客原题　源码

讲解章节：模拟、数论基础

一句话

可把数位 x 替换成 x^2（仅当 x^2 < 10），问能否被 9 整除。

解题思路¶

这题考什么¶

两步化简，把一个「1e5 位大数 + 任意多次操作」的问题压成 81 次判断。

第一步，整除 9 只看数位和：一个数模 9 等于它各位数字之和模 9 （因为 10 ≡ 1 (mod 9)，见 85-基础数学与递推）。于是整个大数可以扔掉，只留下数位和 S。

第二步，看清操作到底能做什么。x^2 < 10 只对 x ∈ {0,1,2,3} 成立：

0 -> 0（数位和 +0）    1 -> 1（数位和 +0）
2 -> 4（数位和 +2）    3 -> 9（数位和 +6）

所以 0 和 1 换了等于没换，真正有用的操作只有两种：把某个 2 变成 4（S 加 2），把某个 3 变成 9（S 加 6）。每个 2、每个 3 各自最多用一次（换过之后变成 4 和 9，不再满足 x^2 < 10）。

设原串有 c2 个 2、c3 个 3，问题就变成：是否存在 0 <= i <= c2、 0 <= j <= c3，使得 (S + 2i + 6j) % 9 == 0。

枚举范围还能再砍：2i mod 9 随 i 每 9 步循环一次，6j mod 9 随 j 每 3 步循环一次，所以 i、j 各取到 8 就已覆盖全部余数，把 c2、c3 截断到 8 之后每组最多 9*9 = 81 次判断，与串长完全无关。

数据规模与复杂度¶

t <= 1e4，∑|n| <= 1e5。每组的开销是「扫一遍串求数位和 + 至多 81 次取模」，总复杂度 O(∑|n| + 81t)，其中 81t 约 8e5 次整数运算，绰绰有余。

坑在哪¶

不要把 1e5 位的串转成 int 再取模。Python 的 int(s) 对超长十进制串是超线性的（且新版本默认还有 4300 位的转换上限），而数位和只要一次线性扫描，两者不是一个量级；
4 及以上的数字平方都 >= 10，不能替换；0 和 1 替换后数位和不变，把它们也算进可用操作会白白扩大枚举范围（结果不会错，但没必要）；
c2、c3 截断到 8 是因为余数循环，不是「取个够大的数」—— 若换成截断到 1，6j 的三种余数就取不全，会漏解；
sum(s) 对 bytes 得到的是各字节的 ASCII 值之和，要减去 48 * 长度才是数位和，少减一次就整体偏移，模 9 的结论全错。

样例复核¶

"322"：S = 3+2+2 = 7，c2 = 2、c3 = 1。取 i = 1、j = 0 得 7 + 2 = 9，被 9 整除 -> YES（对应把一个 2 换成 4，342 = 38 * 9），与样例一致。 "123"：S = 6，c2 = c3 = 1，可得 6、8、12、14，均不被 9 整除 -> NO。

参考实现¶

solutions/BISHI13.py
import sys

data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for k in range(1, t + 1):
    s = data[k]
    total = sum(s) - 48 * len(s)          # bytes 相加再减去 '0' 的偏移 = 数位和
    c2 = min(s.count(50), 8)              # b'2'：2i mod 9 每 9 步循环，截到 8 够用
    c3 = min(s.count(51), 8)              # b'3'：6j mod 9 每 3 步循环，截到 8 更够用
    # 枚举「换掉几个 2、换掉几个 3」，只要有一种组合让数位和被 9 整除即可
    ok = any((total + 2 * i + 6 * j) % 9 == 0
             for i in range(c2 + 1) for j in range(c3 + 1))
    out.append("YES" if ok else "NO")
sys.stdout.write("\n".join(out) + "\n")

BISHI13 九倍平方数¶