Duuuuża liczba w stringu

Question

Dostałem w szkole zadanie aby wypisać  A^b(mod P) (oczywiście po wprowadzeniu a, b, p). Problem pojawia się tutaj: liczba P jest zawsze pierwsza oraz 1 <= A, B <= 10^10^6, 2 <= P < 10^17.

liczby A i B NIE MIESZCZĄ SIĘ nawet w long longu czyli nie mogę wklepać zadania. Podobno można to zapisać w tablicy charów ale nie wiem nawet jak.

Answer 1

Maksymalna liczba z przedziału [ 1 , 10^10^6 ] ma milion cyfr. Na pewno więc nie obejdzie się bez reprezentacji opartej na  std::string i napisaniu własnych podstawowych operacji matematycznych z ich użyciem, lub też (wersja łatwiejsza) wykorzystaniem biblioteki implementującej duże liczby zobacz przykład .

Dalej możesz skorzystać z Little Fermat Theorem -> a^(M-1) ≡ 1 ( mod M ) , gdy M jest liczbą pierwszą