ABC387 E-Digit Sum Divisible 2 题解
chaqjs
·
·
题解
AtCoder Beginner Contest 387 E - Digit Sum Divisible 2题解
题目描述
正整数 n 的位数和定义为 n 写成十进制时的位数和。例如，2025 的位数和是 2 + 0 + 2 + 5 = 9。
如果一个正整数 n 能被它的数位和整除，那么这个正整数 n 就叫做好整数。例如，2025 是一个好整数，因为它能被其数位和 9 整除。
如果 a 和 a+1 都是好整数，那么一对正整数 (a, a+1) 称为孪生好整数。例如，(2024, 2025) 就是一对孪生好整数。
给你一个正整数 N。请找出一对孪生好整数 (a, a + 1)，使得 N \leq a 和 a + 1 \leq 2N。如果不存在这样的一对，输出 -1。
思路
对于小数据，我们进行暴力。而对于大数据，我们只需要构造一个有规律的、比较特殊的数。
首先我们知道：
由此， 我们进行构造。
令一个好整数 a 的数位之和为 8，且个位不为 9。
根据上面的两个性质和好整数的定义，我们可以确定：
即 $(a,a+1)$ 是一对孪生好整数。
归纳一下，使 $(a,a+1)$ 是一对孪生好整数的条件有：
- $a$ 的是 $8$ 的倍数。
- $a$ 的数位之和是 $8$。
- $n \le a < 2n$。
那么，什么样的 $a$ 既是特殊的又满足上面的条件呢？仔细思考，我们发现当 $a$ 的后三位全部是 $0$ 时，既特殊又满足条件。
接下来我们开始分类讨论。
先考虑特殊情况。若 $n$ 除了第一位之外全是 $0$，即 $n = \overline{x00\dots00}$。显然，在构造 $a$ 时，我们可以让 $a$ 的第一位仍为 $x$，第二位为 $8-x$。代码写为 `cout << x << 8 - x, zero_out(len - 2);`。其中 `zero_out` 是输出多少个 $0$。当然，这是建立在 $x \ne 9$ 的基础上的。而当 $x=9$ 时，我们可以让 $a = \overline{1700\dots00}$。代码为 `cout << 17, zero_out(len - 1);`。
若 $n$ 只是一个普通的数呢？我们发现只需要考虑它的前两位即可，我们设为 $x$ 和 $y$。当 $x=9$ 时，与上面的一样。`cout << 17, zero_out(len - 1);`。当 $x=8$ 时，`cout << 107, zero_out(len - 2);`。当 $x \ne 1$ 时，`cout << x + 1 << 8 - x - 1, zero_out(len - 2);`。当 $x=1$ 且 $y \ge 5$ 时，`cout << x + 1 << 8 - x - 1, zero_out(len - 2);`。若以上条件都不成立，`cout << 17 , zero_out(len - 2);`。
至此，我们已经全部分类讨论完了，这是完整代码。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
string n;// 由于 n 非常大，我们只能用字符串读入
// 数据小时判断是否为好整数
bool is_good(int x){
int sum = 0, p = x;
while (p) sum += p % 10, p /= 10;
return x % sum == 0;
}
// 输出 0
void zero_out(int num){
for (int i = 1; i <= num; i++) cout << 0;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
int len = n.size();
// 小数据暴力
if (len <= 6){
int now_n = 0;
for (int i = 0; i < len; i++)
now_n = now_n * 10 + n[i] - '0';
for (int i = now_n; i < 2 * now_n; i++){
if (is_good(i) && is_good(i + 1)){
cout << i;
return 0;
}
}
cout << -1;
return 0;
}
/* ________
考虑 n 的特殊情况，即 n = x00...00 */
bool zero = 0;
for (int i = len - 1; i >= 0; i--)
if (n[i] == '0'){
zero = 1;
break;
}
// 分类讨论
if (!zero){
int x = n[0] - '0';
if (x != 9)
cout << x << 8 - x, zero_out(len - 2);
else
cout << 17, zero_out(len - 1);
}
else {
int x = n[0] - '0';
int y = n[1] - '0';
if (x == 9)
cout << 17, zero_out(len - 1);
else if (x == 8)
cout << 107, zero_out(len - 2);
else if (x != 1 || (x == 1 && y >= 5))
cout << x + 1 << 8 - x - 1, zero_out(len - 2);
else
cout << 17, zero_out(len - 2);
}
return 0;
}
```