Konkurs 16.10.10 - Liczby

Liczby

Limit pamięci: 32MB

Dane jest t trójek liczb naturalnych, gdzie i-tą trójkę oznaczmy jako a_i, c_i oraz liczbę p_i, która jest pierwsza. Dla i-tej trójki chcemy policzyć najmniejsze takie całkowite nieujemne b_i, że a_i^b_i ≡ c_i (mod p_i) lub wypisać -1 jeśli takiej liczby nie ma.

Wejście:

Pierwszy wiersz zawiera jedną liczbę naturalną t (1 <= t <= 100) oznaczającą liczbę trójek liczb całkowitych nieujemnych. Każda trójka znajduje się w osobnym wierszu. Oznaczmy trójkę w i+1-szym wierszu po kolei jako a_i, c_i oraz liczbę pierwszą p_i. Każda z liczb w trójce jest mniejsza bądź równa 10⁹.

Wyjście:

Wyjście powinno zawierać t wierszy, w wierszu o numerze i powinna znajdować się najmniejsza taka liczba całkowita nieujemna b_i, że a_i^b_i ≡ c_i (mod p_i) lub -1 jeśli takiej liczby nie ma.

Przykład:

Dla wejścia:

5
11 13 19
4 3 5
5 1 11
1 1 2
2 4 5

poprawnym wyjściem jest:

-1
-1
0
0
2

[Zgłoś rozwiązanie] [Moje zgłoszenia]

2023-10-02 9:10:06

Kółko informatyczne
Marek Sommer, Joanna Śmigielska,
Maciej Matraszek, Michał Adamczyk, Maciej Dębski