Implementując szkolne mnożenie pisemne nie da się rozwiązać tego zadania w czasie oczekiwanym przez spoj, nawet stosując obliczone wcześniej tablice modulo i mnożenia (próbowałem!).
Tutaj nie ma sensu wymyślanie własnego alogorytmu, conajwyżej można napisać własną implementację jednego z najszybszych znanych algorytmów:
1) Schönhage-Strassen SSA
2) Tom-Cook
3) Karatsuba – Karatsuba c implementation
4) FFT – Mutliplication using fft
Warto pamiętać że każdy z tych algorytmów ma swój przedział w którym jest najlepszy, ale dla tego zadania wszystkie powyższe będą ok.
Zadanie można submitować również w Javie, a ta w klasie BigInteger udostępnia metodę multiply() która dopasowuje rozmiar podanych liczb do najszybszych znanych algorytmów, ale to trochę mało dydaktyczne.
Źródła:
Przydał się parę razy do testów:
Rozpisanie istniejących algorytmów:
1)
0xdbeef's cubicle 