Zadanie : euklid-d
Zadanie

Dana jest liczba całkowita dodatnia n i ciąg n par liczb całkowitych.

Napisz program, który dla każdej podanej pary liczb k oraz a obliczy NWD(k, a) oraz wyznaczy jeśli istnieje taką liczbę b, że (a*b) mod k=1.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu 1..200000.

Wyjście

Wyjście zgodne z przykładem.

Przykład

Dla danych podanych na wejściu:

5
289 202
806 5
910 551
128 77
227 48

Poprawną odpowiedzią jest wyjście:

a=202 k=289 202*93(mod 289)=1
a=5 k=806 5*645(mod 806)=1
a=551 k=910 551*801(mod 910)=1
a=77 k=128 77*5(mod 128)=1
a=48 k=227 48*175(mod 227)=1

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.1 s
Limit pamięci      : 32 MB
Słowa niedozwolone :