Помогите, моя программы по мнению тестовой системы Сириуса работает слишком долго. Помогите ускорить мою программу. Вот само задание:
Обратное число
В этой задаче нужно ответить на 1≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<b<p, такое что (a⋅b−1) ⋮ p.
Входные данные:
В первой строке дано целое число t — количество запросов. В следующих t строках даны по два числа pi и ai, i=1,... ,t.
Выходные данные:
Выведите: t целых чисел (каждое число в отдельной строке) — ответы на запросы.
Примеры:
Ввод:
4
5 1
5 2
5 3
5 4
Вывод:
1
3
2
4
Ограничения: Время выполнения: 5 секунд
Вот мой код:
b = []
for x in range(int(input())):
a = list(map(int, input().split()))
b.append((a[1]) ** (a[0] - 2) % a[0])
print('\n'.join(map(str, b)))
b.append(pow(a[1], a[0] - 2, a[0]))
, но работать она все равно будет некорректно. В условии не сказано, что модуль - простое число, а это необходимое условие для того, чтобы a^(p-2) было сравнимо с a^(-1) по модулю p. Воспользуйтесь расширенным алгоритмом Евклидачисло p является простым
.