首页 > 试题广场 >

九倍平方数

[编程题]九倍平方数

热度指数：99 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个不含前导零的十进制数字串 $n$ （长度 $\leqq10^5$ ）。你可以多次执行以下操作：
$\hspace{23pt}\bullet\,$ 选择 $n$ 中的某一位数字 $x\ (0\leqq x\leqq9)$ ；
$\hspace{23pt}\bullet\,$ 若 $x^2<10$ ，将该位替换为 $x^2$ 。

$\hspace{15pt}$ 若通过若干次（可为 $0$ 次）操作可以使最终数字能被 $9$ 整除，则称数字串 $n$ 为好数。判断每个测试用例的数字串 $n$ 是否为好数。

输入描述:

第一行输入整数 ，表示测试用例数量。
随后  行，每行一个数字串 ，长度 ，保证所有用例数字串  的总长度 。

输出描述:

对每个用例输出 ```` 或 ````（大写），表示是否存在操作序列使得最终数字能被  整除。

示例1

输入

9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632

输出

NO
YES
YES
NO
NO
YES
NO
YES
YES

说明

在第一组样例中，从整数  中只能得到  、  、  和  ，它们都不能被  整除。

在第二组样例中，需要将第二个数字替换为它的平方，那么  就等于  。

在第三组样例中，整数已经可以被  整除。

算法知识视频讲解

K1m4stx

t = int(input())
def solve():
    s =list(map(int, input()))
    total = sum(s)
    f = total
    # print(total)
    if total%9==0:
        print("YES")
        return
    h = {
        2:0,
        3:0
    }
    for i in s:
        if i==2:
            h[2]=h[2]+1
        elif i==3:
            h[3]=h[3]+1
    # print(h)
    for i in range(h[2]+1):
        for j in range(h[3]+1):
            total = total + i*2 + j*6
            # print(total)
            if total%9==0:
                print("YES")
                return
            else:
                total = f
    print("NO")    
for _ in range(t):
    solve()

# 呃呃

发表于 2025-06-25 03:38:29 回复(0)