做此题必备知识 : 整数N能被9整除<=>
N各数位上的数之和能被9整除
假设N的数位和为sum, 要添加的数字x就满足 (x+sum) % 9 == 0, 因此x很容易求: x = 9 - sum%9
但这里要分类讨论
- 当
sum % 9 == 0
时, 此时N已经能被9整除, 所以x应该为0, - 当
sum % 9 != 0
时,x = 9 - sum%9
接下来的任务就是把x添加到N的某个位置上, 且要使结果最小
结论 : 我们要找到一个位置i
, 使得[0, i-1]每个数位上的数都要小于等于x;
如N = 12345, x = 3(随便举的例子, 不满足题目条件), 要使结果最小, x 应该加到123
的后面, 最小的结果为123345
, 可以自行验证
到此题目中所有问题均已解决, 只剩代码实现
AC代码
//
// Created by trudbot on 2022/8/6.
//
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
for(int t=1; t<=T; t++)
{
string num; cin >> num;
int sum = 0;
for (auto &ch: num) sum += ch - '0';
if(sum % 9 == 0) {
num.insert(1, "0");//将0插到第二位
}
else {
string s;
s.push_back('9' - sum%9);//为了便于插入, 用字符串保存要插入的字符
int i = 0;
while (i < num.size() && num[i] <= s[0]) i++;//寻找插入位置
num.insert(i, s);
}
printf("Case #%d: ", t);
cout << num << endl;
}
return 0;
}