首页 > 试题广场 >

九倍平方数

[编程题]九倍平方数
  • 热度指数：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 整除。
算法知识视频讲解
添加回答
C
黎佳沐深头像 黎佳沐深 
#include <stdio.h>
#include <string.h>
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        char n[100005];
        scanf("%s",n);
        long long sum=0;
        int len=strlen(n),num2=0,num3=0,flag=0;
        for(int i=0;i<len;i++){
            sum+=n[i]-'0';
            if(n[i]=='2'){
                num2++;
            }
            else if(n[i]=='3'){
                num3++;
            }
        }
        if(sum%9==0){
            printf("YES\n");
        }
        else{
            flag=0;
            for(int i=0;i<=num2;i++){
                for(int j=0;j<=num3;j++){
                    if((sum+i*2+j*6)%9==0){
                        printf("YES\n");
                        flag=1;
                        break;
                    }
                }
            }
            if(flag==0){
                printf("NO\n");
            }
        }
    }
    return 0;
}
这哪有问题呀 一个用例都没过😭😭救救孩子
发表于 今天 18:23:40 回复(0)
C
yz海头像 yz海
#include <stdio.h>
#include <string.h>
int main() {
    int n;
    char ch[100001];
    int m=0,k=0;
    long long sum=0;
    int n2=0,n3=0,flag=0,r=0,target_mod=0,max_a=0,max_b=0;
    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++)
    {
        m=0;sum=0;n2=0;n3=0;flag=0;k=0;target_mod=0;max_a=0;max_b=0;r=0;
        fgets(ch, sizeof(ch), stdin);
        ch[strcspn(ch, "\n")] = '\0';
        while(ch[m]!='\0')
        {
            if(ch[m]=='2')
            {
                n2++;
            }
            if(ch[m]=='3')
            {
                n3++;
            }
            sum+=ch[m]-'0';
            m++;
        }
        r=sum%9;
        if(r==0)
        {
            printf("YES\n");
            continue;
        }
        target_mod = (9 - r) % 9;
        max_a = (n2 < 9) ? n2 : 8;
        max_b = (n3 < 3) ? n3 : 2;
        for(int a=0;a<=max_a;a++)
        {
            int break_outer = 0;
            for(int b=0;b<=max_b;b++)
            {
                if((2*a + 6*b) %9 == target_mod)
                {
                    flag=1;
                    break_outer = 1;
                    break;
                }
            }
            if(break_outer) break;
        }
        if(flag)
        {
            printf("YES\n");
        }
        else
            printf("NO\n");
    }

    return 0;
}
1. 利用模运算的周期性，减少枚举范围
关键观察：
操作对总和的增量是 2a + 6b（a 是数字 2 的使用次数，b 是数字 3 的使用次数），而我们只关心这个增量对 模 9 的结果（因为目标是让 (初始总和 + 增量) % 9 == 0）。
2a % 9 的可能结果：仅与 a % 9 有关（因为 2*(a+9) %9 = (2a + 18) %9 = 2a%9）。
6b % 9 的可能结果：仅与 b % 3 有关（因为 6*(b+3) %9 = (6b + 18) %9 = 6b%9）。
因此，a 只需枚举 0~min(n2, 8)（超过 9 的部分重复模 9 结果），b 只需枚举 0~min(n3, 2)（超过 3 的部分重复模 9 结果），循环次数从 n2*n3 降至 9*3=27 次，效率极大提升。
2. 提前计算目标模值，简化判断条件
设初始总和的模 9 余数为 r = sum % 9，我们需要增量 2a + 6b 满足：
(r + 2a + 6b) % 9 == 0
即 (2a + 6b) % 9 == (9 - r) % 9（记为 target_mod）。
循环中只需判断 (2a + 6b) %9 是否等于 target_mod，无需每次计算与 r 的和，逻辑更清晰。
3. 循环内提前 break，避免无效计算
当找到一组有效的 a 和 b 时（即满足模 9 条件），可以立即跳出所有循环，无需继续枚举其他可能，减少不必要的计算。
发表于 2025-10-21 16:55:23 回复(1)
C
牛客102905454号头像 牛客102905454号
为什么我的代码无法通过最后一个测试例呀，显示段错误
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    int t;
    scanf("%d",&t);

    while(t--){
        char *str = (char*)malloc(100001 * sizeof(char));
        scanf("%s",str);
        int length = strlen(str);
        int num2 = 0;
        int num3 = 0;
        int sum = 0;

        for(int i = 0; i < length; i++){
            int temp = str[i] - '0';
            sum += temp;
            if(temp == 2){
                num2++;
            }
            if(temp == 3){
                num3++;
            }
        }

        int flag = 0;

        for(int i = 0; i <= num2; i++){
            if(flag == 1)break;
            for(int j = 0; j <= num3; j++){
                int ans = sum + i * 2 + j * 6;
                if(ans % 9 == 0){
                    flag = 1;
                    printf("YES\n");
                    break;
                }
            }
        }

        if(flag == 0){
            printf("NO\n");
        }

        free(str);
    }
} 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    int t;
    scanf("%d",&t);

    while(t--){
        char *str = (char*)malloc(100001 * sizeof(char));
        scanf("%s",str);
        int length = strlen(str);
        int num2 = 0;
        int num3 = 0;
        int sum = 0;

        for(int i = 0; i < length; i++){
            int temp = str[i] - '0';
            sum += temp;
            if(temp == 2){
                num2++;
            }
            if(temp == 3){
                num3++;
            }
        }

        int flag = 0;

        for(int i = 0; i <= num2; i++){
            if(flag == 1)break;
            for(int j = 0; j <= num3; j++){
                int ans = sum + i * 2 + j * 6;
                if(ans % 9 == 0){
                    flag = 1;
                    printf("YES\n");
                    break;
                }
            }
        }

        if(flag == 0){
            printf("NO\n");
        }

        free(str);
    }
}
发表于 2025-09-13 19:45:59 回复(1)
提交观点

问题信息

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

热门推荐

相关试题

九倍平方数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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