- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
def karatsuba_multiplication(x : int, y : int) -> int:
sx, sy = map(lambda x: '0' + str(x) if len(str(x)) % 2 != 0 else str(x), (x, y))
return _karatsuba_multiplication(sx, sy, max(len(sx), len(sy)))
def _prepend_nils(string : str, amount_of_nils : int) -> str:
return ('0' * amount_of_nils + string)
def _karatsuba_multiplication(x : str, y : str, n : int) -> int:
x, y = map(lambda x: _prepend_nils(x, (n - len(x))), (x, y))
if (n == 1):
return (int(x) * int(y))
mid = n // 2
a, b = int(x[:mid]), int(x[mid:])
c, d = int(y[:mid]), int(y[mid:])
p = a + b
q = c + d
ac = _karatsuba_multiplication(str(a), str(c), max(len(str(a)), len(str(c))))
bd = _karatsuba_multiplication(str(b), str(d), max(len(str(b)), len(str(d))))
pq = _karatsuba_multiplication(str(p), str(q), max(len(str(p)), len(str(q))))
adbc = pq - ac - bd
return 10**n * ac + 10**(mid + n % 2) * adbc + bd
JloJle4Ka 10.04.2021 13:39 # 0
gologub 10.04.2021 14:19 # +1
booratihno 10.04.2021 14:22 # 0
CEO -- seo
bootcamp_dropout 10.04.2021 14:25 # +1
booratihno 10.04.2021 14:28 # +1
gologub 10.04.2021 15:28 # +4
Drug -- друг
Examine -- экзамен
Faggot -- фагот
Most -- мост
Piston -- пистон
Resin -- резина
Sewer -- север
Tort -- торт
Velvet -- вельвет
Steve_Brown 13.04.2021 13:43 # 0
http://www.govnokod.ru/25095
bormand 10.04.2021 14:05 # +1
JloJle4Ka 10.04.2021 14:07 # 0
bormand 10.04.2021 14:11 # +1
j123123 10.04.2021 17:05 # 0
JloJle4Ka 12.04.2021 16:52 # +1
bormand 12.04.2021 16:55 # +1
gologub 12.04.2021 16:59 # +1
guest6 10.04.2021 14:16 # +1
bormand 12.04.2021 16:56 # +1
guest6 12.04.2021 17:09 # 0
Если хранить числа по 9 десятичных знаков (только тут не уверен, что норм хранить в десятичных), то около ста интов получится.
bormand 12.04.2021 17:11 # +2
У FFT оверхед адовый, оно не окупается для мелочи.
DypHuu_niBEHb 12.04.2021 17:17 # +1
bormand 12.04.2021 17:22 # 0
gologub 12.04.2021 17:44 # 0
guest6 12.04.2021 17:10 # 0
booratihno 10.04.2021 14:42 # +2
bormand 12.04.2021 17:00 # 0