Карацуба
(---A1----) (---A2---)
(---B1----) (---B2---)
A = A1 * BASE^k + A2
B = B1 * BASE^k + B2
A*B = A1*B1*BASE^{2k} +
A2*B2 +
((A1+A2)(B1+B2) - A1*B1 - A2*B2)*BASE^k
---------------------------------------------------
Умножаем многочлены! => короткий код
BASE = 10^6
BASE^2 * LEN < 10^{18} <= 2^{63}
LEN = 262144 / k <= 10^5
---------------------------------------------------
LEN <= 8
LEN^2 быстрее Карацубы