ABC387E Another Solution With Brute Force

猜测：当解的很多位不为

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 很慢。

PYTHON

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

ABC387E Another Solution With Brute Force

文章操作

相关推荐

评论

ABC387E Another Solution With Brute Force