Кроме того, насколько я знаю, вы не получите намного лучше, чем простой линейный алгоритм O (n), т.е. просто добавьте цифру за цифрой. Вероятно, вам все равно придется читать весь ввод, так что он по крайней мере линейный. Возможно, вам удастся сделать разные трюки, чтобы уменьшить константу.
Ваша главная проблема - умножение из-за квадратичной природы основного алгоритма длинного умножения. Возможно, вы захотите рассмотреть один из нескольких гораздо более быстрых методов, приведенных здесь . Метод Карацубы немного сложен в реализации, но, вероятно, это самый простой нетривиальный алгоритм, который даст вам выигрыш. В противном случае вам придется более подробно изучить методы быстрого преобразования Фурье, такие как алгоритм Шёнхаге-Штрассена или алгоритм Фюрера .
См. Также Большая буква O .