题目链接

九倍平方数

题目描述

给定一个不含前导零的十进制数字串 （长度 ）。你可以多次执行以下操作：

  • 选择 中的某一位数字 。
  • 将该位数字替换为 。如果 是一个多位数（例如 ），它会替换掉原来的单个数字 ，从而可能改变数字串的长度。

若通过若干次（可为 0 次）操作可以使最终数字能被 9 整除，则称数字串 为好数。判断给定的数字串 是否为好数。

输入:

  • 第一行输入整数 ，表示测试用例数量。
  • 随后 行，每行一个数字串 。

输出:

  • 对每个用例输出 YES 或 NO。

解题思路

本题的核心依然是利用数字可被9整除的性质：一个数能被9整除，当且仅当它的各位数字之和能被9整除。

设原数各位数字之和为 。我们的目标是通过操作，使得最终的数字之和是9的倍数。操作是将数字 替换为 ，这会使数字之和模9的结果发生变化。这个变化量 等于 。

根据给出的正确解法，我们得到了一个关键的简化思路：我们实际上只需要考虑对数字串中的数字 2 和 3 进行操作。其他数字的操作可以被忽略或等效替代。

  • 对数字 2 操作，产生的变化量 。
  • 对数字 3 操作，产生的变化量 。

解题步骤如下：

  1. 计算初始数字串 的各位数字之和，并得到它模9的余数 。
  2. 如果 ，数字本身就能被9整除，直接输出 YES。
  3. 否则，计算目标变化量 target_delta，使得 。显然，target_delta = 。
  4. 统计数字串 中数字 2 的个数 和数字 3 的个数 。
  5. 通过两层循环，枚举使用 个 2 和 个 3 来进行操作，其中 ，。
  6. 检查是否存在一对 使得总变化量 等于 target_delta。如果找到，说明是好数，输出 YES 并结束。
  7. 为了优化，可以注意到变化量具有周期性。使用9次 效果等于不使用。使用3次 效果等于不使用。因此，循环的上限可以分别设为 和 。
  8. 如果遍历完所有组合都找不到满足条件的，则输出 NO。

代码

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

bool isGoodNumber(const string& s) {
    long long sum_digits = 0;
    int cnt2 = 0;
    int cnt3 = 0;
    for (char c : s) {
        int digit = c - '0';
        sum_digits += digit;
        if (digit == 2) {
            cnt2++;
        } else if (digit == 3) {
            cnt3++;
        }
    }

    int r_init = sum_digits % 9;
    if (r_init == 0) {
        return true;
    }

    int target_delta = (9 - r_init) % 9;

    for (int i = 0; i <= min(cnt2, 8); ++i) {
        for (int j = 0; j <= min(cnt3, 2); ++j) {
            if ((i * 2 + j * 6) % 9 == target_delta) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        if (isGoodNumber(s)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {

    public static boolean isGoodNumber(String s) {
        long sumDigits = 0;
        int cnt2 = 0;
        int cnt3 = 0;
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            sumDigits += digit;
            if (digit == 2) {
                cnt2++;
            } else if (digit == 3) {
                cnt3++;
            }
        }

        int r_init = (int)(sumDigits % 9);
        if (r_init == 0) {
            return true;
        }

        int target_delta = (9 - r_init) % 9;

        for (int i = 0; i <= Math.min(cnt2, 8); i++) {
            for (int j = 0; j <= Math.min(cnt3, 2); j++) {
                if ((i * 2 + j * 6) % 9 == target_delta) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            String s = sc.next();
            if (isGoodNumber(s)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

import sys

def is_good_number(s):
    sum_digits = 0
    cnt2 = 0
    cnt3 = 0
    for char_d in s:
        digit = int(char_d)
        sum_digits += digit
        if digit == 2:
            cnt2 += 1
        elif digit == 3:
            cnt3 += 1
    
    r_init = sum_digits % 9
    if r_init == 0:
        return True
        
    target_delta = (9 - r_init) % 9
    
    for i in range(min(cnt2, 8) + 1):
        for j in range(min(cnt3, 2) + 1):
            if (i * 2 + j * 6) % 9 == target_delta:
                return True
    
    return False

t = int(input())
for _ in range(t):
    s = input()
    if is_good_number(s):
        print("YES")
    else:
        print("NO")

算法及复杂度

  • 算法：数学 + 枚举
  • 时间复杂度：对于每个测试用例，设数字串长度为 。我们需要遍历一次字符串来计算初始余数和 2、3 的计数，这需要 。然后进行一个常数次迭代的循环（最多 次）来检查是否存在解。总时间复杂度为 。
  • 空间复杂度：，只需要存储几个计数器变量。