python - 添加两个大数字(一百万位)的最快方法

Question

约束:

1 ≤ 𝐴 ≤ 𝐵 ≤ 10^1000000

输入:

1000211 1000299

输出:

2000510

运行时间必须 <4 秒。

我已经试过了，但还是太慢了:

x, y = input().split()
print(int(x) + int(y))

Answer 1

您正在从十进制转换为二进制并返回。至少在 CPython 中，这需要二次时间(或导致错误)。代替 int，使用 Decimal ，在配置“bignum 算术”后，如该页面末尾附近所示。然后它需要线性时间。

两个数字都在限制的步骤的时间:

int() 14.1069 seconds
add    0.0005 seconds
str() 15.9351 seconds
print  0.0019 seconds

使用 Decimal 作为 int:

int()  0.0366 seconds
add    0.0001 seconds
str()  0.0043 seconds
print  0.0009 seconds

代码(Try it online!):

from time import time
from contextlib import redirect_stdout
import io

# Set to True for using Decimal as int (a hack to overwrite it like that, but meh, who cares here)
if False:
    from decimal import *
    setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX, Emin=MIN_EMIN))
    int = Decimal

def report(label):
    global t
    print(label, f'{time() - t:7.4f} seconds')
    t = time()

x = y = '9'*999999
t = time()
x, y = int(x), int(y)
report('int()')
s = x + y
report('add  ')
s = str(s)
report('str()')
with open('/dev/null', 'w') as devnull:
    with redirect_stdout(devnull) as f:
        print(s)
report('print')