题解：P16870 [GKS 2022 #A] Challenge Nine

Alexlulu · 2026-06-10 20:53:22 · 题解

题目传送门 & 更好的阅读体验

当一个整数 \overline{x_1x_2\dots x_L} 是 9 的倍数时，\displaystyle\sum_{i=1}^L x_i 一定也是 9 的倍数，因此我们可以直接把 N 作为字符串输入并统计其数字和对 9 取模的结果，然后就可以得到我们需要添加的数字。

接着，我们来考虑如何最小化修改后的 N 值。我们需要使得添加的数字 x 和添加后的前一位数字 l 和后一位数字 r 满足 l \le x \le r（如果没有前一位数字，则令 l=0，如果没有后一位数字，则令 r=+\infty），通过遍历即可实现。最后一定要记得考虑前导 0 的情况。

:::success[AC 代码]{open}

#include <bits/stdc++.h>
using namespace std;

int T, sum, x;
string s; // 将 N 作为字符串输入

int Alexlulu()
{
    cin.tie(0) -> sync_with_stdio(false); // 快读
    cin >> T;
    for (int cs = 1; cs <= T; cs++)
    {
        cin >> s; // 输入 N
        sum = 0;
        for (char c : s) sum = (sum+c-'0') % 9; // 求 N 的数字和对 9 取模的结果
        x = (9 - sum) % 9; // 求需要添加的数字，记得 % 9
        cout << "Case #" << cs << ": "; // 按格式输出
        bool flag = false, ok = false; // flag 记录是否为第一位，ok 记录是否已添加
        for (char c : s) // 遍历
        {
            if (!ok && c-'0' > x && !(!x && !flag)) // 未添加 && 原数 > 添加数 && 不是前导 0
            {
                cout << x; // 直接输出添加数
                ok = true; // 标记已添加
            }
            cout << c; // 输出原数
            flag = true; // 标记不是第一位
        }
        if (!ok) cout << x; // 添加在最后的情况
        cout << '\n'; // 换行不要忘
    }
    return 0;
}

:::