Оптимизировать код (Обратное число)

@xquzZ · Регистрация: 29.06.2022

Студворк — интернет-сервис помощи студентам

В этой задаче нужно ответить на 1≤t≤10^5 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤10^9 и 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

Вот мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
 
int main()
{
int t, p, a, b;
cin >> t;
int var = 0;
vector <int> v(t);
for (int i = t; i>0; i--){
  cin >> p >> a;
  for (int i = p-1; 0 < i < p; i--){
    if ((a*i-1)%p==0){
        b=i;
        break;
    }
  }
  v[var]=b;
  var++;
}
var = 0;
for (int i = t; i>0; i--){
cout << v[var] << endl;
var++;
}
return 0;
}

Ограничения
Время выполнения: 5 секунд

нигде не нашел решения, так что прошу помочь с оптимизацией.

@p1rfect · 25.07.2022, 21:16

xquzZ, если не трудно можешь скинуть код который придумал? или так и оставил?

@depressed0yokid · 30.07.2022, 01:55

Байт, в этом коде банально переполнение в этих двух строчках:

C++
1
2
result = (result*value)%m;
value = (value*value)%m;

Добавлено через 21 минуту
xquzZ, проверь мой вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
int power(int base, int pow, int mod) {
    if (pow == 0) {
        return 1;
    }
    if (pow % 2 == 0) {
        int result = power(base, pow / 2, mod);
        return (int64_t)result * result % mod;
    } else {
        return (int64_t)power(base, pow - 1, mod) * base % mod;
    }
}
 
int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int p, a;
        std::cin >> p >> a;
        std::cout << power(a, p - 2, p) << std::endl;
    }
}

@xquzZ · 01.08.2022, 11:48 **[ТС]**

Сообщение от p1rfect

xquzZ, если не трудно можешь скинуть код который придумал? или так и оставил?

я как-то подзабил на задание это, тем более время вышло

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@p1rfect 0 / 0 / 0 Регистрация: 25.07.2022 Сообщений: 14
	25.07.2022, 21:16
	xquzZ, если не трудно можешь скинуть код который придумал? или так и оставил? 0