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

@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, если не трудно можешь скинуть код который придумал? или так и оставил?

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

Новые блоги и статьи Все статьи Все блоги /
Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .
Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .

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

Опции темы