题解：[ABC387E] Digit Sum Divisible 2
可以尝试通过构造解决此题。
考虑到一个数能被 $9$ 整除是各个数位上和为 $9$ 的倍数，一个数整除 $8$ 只需要末三位均为 $0$ 即可。因此大致的方向就是去构造 $x,8 - x,0,0,\cdots,0,0,0$ 的一个数来满足条件。
【为什么选择 $8$：相较于 $4$，$8$ 的拆分比较多，因此更容易满足条件。】
再来考虑 $[N,2N]$ 这个范围的限制。设 $N$ 的最高位 $p$，则：
当 $p \ge 7$ 时，构造 $107\underbrace{00\cdots000}_{n-2}$ 总能符合条件。
当 $2 \le p \le 7$ 以及 $17,18,19$ 开头的数，构造 $p + 1,7 - p,\underbrace{0,0,\cdots,0,0,0}_{n - 2}$ 总能符合条件。
$p=1$ 的其余情况，构造 $17\underbrace{00\cdots000}_{n-2}$ 总能符合条件。
当然，$N$ 较小的时候难以构造出上述条件，直接跑暴力即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n;char s[MAX];
int calc (int x)
{
int res = 0;
while (x) res += x % 10,x /= 10;
return res;
}
int main ()
{
scanf ("%s",s + 1);n = strlen (s + 1);
if (n <= 6)
{
int num = 0;
for (int i = 1;i <= n;++i) num = num * 10 + s[i] - '0';
for (int i = num;i < 2 * num;++i)
if (i % calc (i) == 0 && (i + 1) % calc (i + 1) == 0) {printf ("%d\n",i);return 0;}
puts ("-1");
return 0;
}
if (s[1] >= '7')
{
printf ("107");
for (int i = 1;i <= n - 2;++i) printf ("0");
puts ("");
}
else if (s[1] >= '2' || (s[1] == '1' && s[2] >= '7'))
{
int dig = s[1] - '0' + 1;
printf ("%d%d",dig,8 - dig);
for (int i = 1;i <= n - 2;++i) printf ("0");
puts ("");
}
else
{
printf ("17");
for (int i = 1;i <= n - 2;++i) printf ("0");
puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
