Question

СРОЧНО! ПИТОН! ОТДАЮ ВСЕ БАЛЛЫ! Обратное числоВ этой задаче нужно ответить на 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 секунд

Answer 1

Ответ:

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)))

Объяснение:

Эта программа зашла.

Answer 2

Конечно, я могу помочь вам с этой задачей. Вам нужно решить задачу "Обратное число" для каждого запроса. В данной задаче требуется найти число b для каждого запроса такое, что (a * b) % p = 1.

Приведу пример кода на Python, который выполняет данную задачу:

pythonCopy code
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extended_gcd(b, a % b)
        return d, y, x - y * (a // b)

def find_inverse(a, p):
    _, x, _ = extended_gcd(a, p)
    return x % p

t = int(input())
for _ in range(t):
    p, a = map(int, input().split())
    b = find_inverse(a, p)
    print(b)

Вы можете вставить этот код в свою среду разработки Python и выполнить его, предварительно введя количество запросов и сами запросы. Код использует расширенный алгоритм Евклида для нахождения обратного числа по модулю.