3

Помогите, моя программы по мнению тестовой системы Сириуса работает слишком долго. Помогите ускорить мою программу. Вот само задание:

Обратное число

В этой задаче нужно ответить на 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)))
6
  • 1
    Каким образом из ввода получается вывод? Причём здесь обратное число и что это такое? 2 июн 2020 в 20:12
  • Программу можно ускорить так b.append(pow(a[1], a[0] - 2, a[0])), но работать она все равно будет некорректно. В условии не сказано, что модуль - простое число, а это необходимое условие для того, чтобы a^(p-2) было сравнимо с a^(-1) по модулю p. Воспользуйтесь расширенным алгоритмом Евклида
    – extrn
    3 июн 2020 в 4:07
  • 1
    @extrn, число p является простым.
    – Qwertiy
    16 июн 2020 в 23:55
  • @Qwertiy видимо начинаю слепнуть :)
    – extrn
    17 июн 2020 в 0:59
  • @MBo, не дубликат. Там условия другие - ни простота модуля не гарантируется, ни существование обратного.
    – Qwertiy
    17 июн 2020 в 12:27

1 ответ 1

2

Длинная арифметика медленная. А по условию тебе вообще не нужны числа больше 109 (и 1018 в промежуточных операциях). Так что придётся использовать бинарное возведение в степень по модулю.

1
  • @extrn, я не знаток питона и не знал, что там такая есть. Удалил из ответа часть про самостоятельную реализацию.
    – Qwertiy
    17 июн 2020 в 12:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.