Носорог! Противоположное число В этой задаче требуется ответить на 1 ≤ t ≤ 10^5 запросов. Каждый запрос состоит из двух

Противоположное число:
Задача требует найти целое число b, удовлетворяющее условию (a * b - 1) mod p = 0. Идея заключается в том, чтобы искать такое число b, для которого выполняется равенство (a * b - 1) mod p = 0, то есть (a * b) mod p = 1.

Одним из подходов к решению этой задачи является использование расширенного алгоритма Евклида для нахождения мультипликативно обратного элемента a^-1 по модулю p. Он позволяет найти целое число b, такое что (a * b) mod p = 1.

Алгоритм можно представить в виде рекурсивной функции gcdExtended(a, b), которая возвращает целые числа x, y и d, где d - наибольший общий делитель (НОД) a и b, и выполняется равенство a * x + b * y = d. Если d равно 1, то x является мультипликативно обратным элементом a по модулю p.

Для каждого запроса циклом проходим по всем числам a и находим их противоположные значения b с использованием расширенного алгоритма Евклида. Результат выводится на экран.

Пример использования:
- Входные данные:
3
11 3
13 5
17 7

- Выходные данные:
4
8
10

Советы:
- Перед использованием расширенного алгоритма Евклида, следует убедиться, что число p является простым.
- При реализации алгоритма следует учесть ситуацию, когда d > 1. В таком случае обратного элемента не существует.

Упражнение:
Сообщите противоположные числа b для запросов с числами p и a:
1. p = 7, a = 3
2. p = 19, a = 6
3. p = 23, a = 10