Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ODWROTNO - Odwrotność liczby

Cialo Z_p zawiera liczby { 0, 1, ..., p-1 }, gdzie p jest liczbą pierwszą.

Napisz program, który znajduje odwrotność liczby n w ciele liczb Z_p.
Odwrotnością liczby n jest taka liczba m, że 
  ( n*m ) mod p = 1



Wejście:
W pierwszym wierszu danych znajduje się liczba zestawów danych T ( 1 <= T <= 100 ).
Każdy zestaw danych podany jest w osobnym wierszu zawierającym dwie liczby
oddzielone spacją : p i n ( 1 <= n < p-1,  p < 10^9)

Przykład

Wejście:
3
5 3
11 5
17 9

Wyjście
2
9
2
Zachęcam do przeczytania notatek na RNO-Wiki o rozszerzonym algorytmie Euklidesa.


Dodane przez:Rafal Nowak
Data dodania:2007-01-14
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:C CPP PAS-FPC TEXT
Pochodzenie:W³asne
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.