专栏文章

ABC387 E-Digit Sum Divisible 2 题解

cchaqjs
AT_abc387_e题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqjnyh2
此快照首次捕获于
2025/12/04 05:54
3 个月前
此快照最后确认于
2025/12/04 05:54
3 个月前
查看原文

AtCoder Beginner Contest 387 E - Digit Sum Divisible 2题解

题目描述

正整数 nn 的位数和定义为 nn 写成十进制时的位数和。例如，20252025 的位数和是 2+0+2+5=92 + 0 + 2 + 5 = 9。
如果一个正整数 nn 能被它的数位和整除，那么这个正整数 nn 就叫做好整数。例如，20252025 是一个好整数，因为它能被其数位和 99 整除。
如果 aa 和 a+1a+1 都是好整数，那么一对正整数 (a,a+1)(a, a+1) 称为孪生好整数。例如，(2024,2025)(2024, 2025) 就是一对孪生好整数。
给你一个正整数 NN。请找出一对孪生好整数 (a,a+1)(a, a + 1)，使得 N≤aN \leq a 和 a+1≤2Na + 1 \leq 2N。如果不存在这样的一对，输出 −1-1。

思路

对于小数据，我们进行暴力。而对于大数据，我们只需要构造一个有规律的、比较特殊的数。
首先我们知道：
  • 一个数能被 88 整除当且仅当它的后三位能被 88 整除。
  • 一个数能被 99 整除当且仅当它的数位之和能被 99 整除。
由此， 我们进行构造。
令一个好整数 aa 的数位之和为 88，且个位不为 99。
根据上面的两个性质和好整数的定义，我们可以确定：
aa 为 88 的倍数，a+1a+1 为 99 的倍数且是一个好整数。
即 (a,a+1)(a,a+1) 是一对孪生好整数。
归纳一下，使 (a,a+1)(a,a+1) 是一对孪生好整数的条件有：
  • aa 的是 88 的倍数。
  • aa 的数位之和是 88。
  • n≤a<2nn \le a < 2n。
那么，什么样的 aa 既是特殊的又满足上面的条件呢？仔细思考，我们发现当 aa 的后三位全部是 00 时，既特殊又满足条件。
接下来我们开始分类讨论。
先考虑特殊情况。若 nn 除了第一位之外全是 00，即 n=x00…00‾n = \overline{x00\dots00}。显然，在构造 aa 时，我们可以让 aa 的第一位仍为 xx，第二位为 8−x8-x。代码写为 cout << x << 8 - x, zero_out(len - 2);。其中 zero_out 是输出多少个 00。当然，这是建立在 x≠9x \ne 9 的基础上的。而当 x=9x=9 时，我们可以让 a=1700…00‾a = \overline{1700\dots00}。代码为 cout << 17, zero_out(len - 1);。
若 nn 只是一个普通的数呢？我们发现只需要考虑它的前两位即可，我们设为 xx 和 yy。当 x=9x=9 时，与上面的一样。cout << 17, zero_out(len - 1);。当 x=8x=8 时，cout << 107, zero_out(len - 2);。当 x≠1x \ne 1 时，cout << x + 1 << 8 - x - 1, zero_out(len - 2);。当 x=1x=1 且 y≥5y \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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...