СРОЧНО! ПИТОН! ОТДАЮ ВСЕ БАЛЛЫ! Обратное числоВ этой задаче нужно ответить на 1≤≤1051≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤≤1092≤p≤109 и 0<<0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<<0<b<p такое, что (⋅−1) ⋮ (a⋅b−1)⋮p.Входные данныеВ первой строке дано целое число t — количество запросов.В следующих t строках даны по два числа pi и ai, =1,…,i=1,…,t.Выходные данныеВыведите t целых чисел (каждое число в отдельной строке) — ответы на запросы.ПримерыВводВывод45 15 25 35 41324ОграниченияВремя выполнения: 5 секунд
t = int(input()) bs = [] for i in range(t): p, a = list(map(int, input().split())) b = str(a ** (p - 2) % p) bs.append(b) print('\n'.join(bs)) я пробовал так но слишком большая вычислительная сложность. Нужно O(log2 p)
Ответ:
b = []
for x in range(int(input())):
a = list(map(int, input().split()))
b.append(pow(a[1], a[0] - 2, a[0]))
print('\n'.join(map(str, b)))
Объяснение:
Эта программа зашла.
а c++?