ABC387E Another Solution With Brute Force

ZnPdCo · 2025-01-04 21:54:59 · 题解

猜测：当解的很多位不为 0 时，数位和也会非常大，那么出现合法的情况概率也会非常低。

所以我们需要让解存在尽量多的 0。

对于 n\le 1000，我们直接暴力判断。

对于 n>1000，我们分类讨论：

• 我们将 n 乘以 2，将这个数的最高位保留，其余数设为 0，将这个数设为 m，然后从 m 开始暴力做；
• 如果上面没有跑出解，说明上述 m 非常接近上界 2\times n，那么 n 一定是由除最高位以外许多位为 0 的数组成。我们直接从 n 开始做。

数量级和正确性证明可以通过官方题解来理解。

@_determination_：这样不会 TLE 吗？

Re：请参考官方题解，发现解都是由前面一些数，中间一堆 0，最后面一些数组成的，而我们从一个除了第一位都是 0 的数开始跑肯定是能够跑出解的，而且如果达到了上界，说明 n 本身就有非常多的 0，所以从 n 开始跑，时间复杂度的正确性是能够保证的。

这种做法只是说如果你懒得推那么多情况，就可以用。

@__xzm__：为啥提交会 TLE

Re：请使用 PyPy 提交，众所周知，CPython 很慢。

import sys
sys.set_int_max_str_digits(0)
def digit_sum(n):
    return sum(int(i) for i in str(n))
n = int(input())
up = n * 2
if n <= 1000:
    a, b = n, n + 1
    while b <= up:
        if a % digit_sum(a) == 0 and b % digit_sum(b) == 0:
            print(a)
            sys.exit(0)
        a += 1
        b += 1
    print("-1")
m = n * 2
m = int(str(m)[0] + (len(str(m)) - 1) * "0")
a, b = m, m + 1
while b <= up:
    if a % digit_sum(a) == 0 and b % digit_sum(b) == 0:
        print(a)
        sys.exit(0)
    a += 1
    b += 1
a, b = n, n + 1
while b <= up:
    if a % digit_sum(a) == 0 and b % digit_sum(b) == 0:
        print(a)
        sys.exit(0)
    a += 1
    b += 1