首页 > 试题广场 >

九倍平方数

[编程题]九倍平方数
  • 热度指数：3283 时间限制：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 是否为好数。

输入描述:
\hspace{15pt}第一行输入整数 t\left(1\leqq t\leqq 10^4\right)，表示测试用例数量。
\hspace{15pt}随后 t 行，每行一个数字串 n，长度 \leqq10^5，保证所有用例数字串 n 的总长度 \leqq10^5。


输出描述:
\hspace{15pt}对每个用例输出 ``\text{YES}`` 或 ``\text{NO}``（大写），表示是否存在操作序列使得最终数字能被 9 整除。
示例1

输入

9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632

输出

NO
YES
YES
NO
NO
YES
NO
YES
YES

说明

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

在第二组样例中，需要将第二个数字替换为它的平方，那么 n 就等于 342 = 38 \cdot 9 。

在第三组样例中，整数已经可以被 9 整除。
算法知识视频讲解
添加回答
Python3
忧伤的双曲线头像 忧伤的双曲线
t = int(input())
for i in range(t):
    n = input()
    num_2 = 0
    num_3 = 0
    sum_others = 0 # 不为2、3数的和
    for j in n:
        j = int(j)
        if j==2:
            num_2 += 1
        elif j==3:
            num_3 += 1
        else:
            sum_others += j
    sum_all = sum_others+2*num_2+3*num_3
    if sum_all%9==0:
        print('YES')
    else:
        flag = False
        for x in range(num_2+1):
            for y in range(num_3+1):
                if (sum_all+2*x+6*y)%9==0:
                    print('YES')
                    flag = True
                    break
            if flag:
                break
        if not flag:
            print('NO')
发表于 2025-08-24 18:30:23 回复(0)
提交观点

问题信息

来自：2025年秋招-中国移...
难度：
1条回答 139浏览

热门推荐

相关试题

九倍平方数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号