Задача Обратное Число:

@TWTwoFace · Регистрация: 13.06.2020

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

Обратное число
В этой задаче нужно ответить на 1≤t≤10⁵ запросов. Каждый запрос состоит из двух целых чисел 2≤p≤10⁹ и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<b<p такое, что (a⋅b−1) ⋮ p.
вот мой код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cmath> 
using namespace std;
 
int main()
{
int arr[100000];
int n;
cin>>n;
long long a,b;
int c;
for(int i = 0; i<n;i++){
    cin>>a>>b;
    c = pow(b,a-2);
    arr[i]= c%a;
}
for(int h = 0;h< n;h++){
    cout<<arr[h]<<endl;
    
}
    return 0;
}

Говорит неверный ответ.

@Super-Hacker · 14.06.2020, 17:46

Все очень просто, возьмем пример

p = 4
a = 2
тогда b = 4 % 2, то есть 0, а нам такое не подходит по условию

@TWTwoFace · 14.06.2020, 20:25 **[ТС]**

Но ведь p по условию простое

@nalbe666 · 14.06.2020, 20:32

TWTwoFace, киньте ссылку на задачу.

@TWTwoFace · 14.06.2020, 21:43 **[ТС]**

ссылки нет могу дать только вот:
Обратное число
В этой задаче нужно ответить на 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 целых чисел (каждое число в отдельной строке) — ответы на запросы.

Примеры
Ввод 1
4
5 1
5 2
5 3
5 4
Вывод
1
3
2
4

@nalbe666 · 14.06.2020, 21:47

Тут, где-то в пределах страницы, лежит пост с такой же задачей и решением.

@little_Ganter · 15.07.2021, 12:45

TWTwoFace, ты решил проблему?
я просто в той же ситуации

@LVV · 15.07.2021, 13:54

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
30
#include <iostream>
using namespace std;
int main()
{
    
    int a, b, p, t;
    cin >> t;
    int *arr = new int[t];
        
    for (int i = 0; i < t; i++)
    {
        cin >> p >> a;
        for (b = 1; b < p; b++)
        {
            if ((a*b - 1) % p == 0)
            {
                arr[i] = b;
                break;
            }
        }
 
    }
 
    for (int i = 0; i < t; i++)
        cout << arr[i] << endl;
 
 
 
    return 0;
}

@dmitrii2000 · 15.07.2021, 16:12

Программа слишком долго выполнялась

Добавлено через 1 час 0 минут
Программа слишком долго выполнялась

@LVV · 15.07.2021, 16:15

Для предложенного Вами условия: "1≤t≤105 2≤p≤109" выполняться не будет долго.
А для: "1≤t≤10^5 2≤p≤10^9" нужно другое решение.

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@Super-Hacker 342 / 114 / 37 Регистрация: 26.11.2019 Сообщений: 735
	14.06.2020, 17:46
	Все очень просто, возьмем пример p = 4 a = 2 тогда b = 4 % 2, то есть 0, а нам такое не подходит по условию 0

@TWTwoFace 0 / 0 / 0 Регистрация: 13.06.2020 Сообщений: 4
	14.06.2020, 20:25 [ТС]
	Но ведь p по условию простое 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	14.06.2020, 20:32
	TWTwoFace, киньте ссылку на задачу. 0

@TWTwoFace 0 / 0 / 0 Регистрация: 13.06.2020 Сообщений: 4
	14.06.2020, 21:43 [ТС]
	ссылки нет могу дать только вот: Обратное число В этой задаче нужно ответить на 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 целых чисел (каждое число в отдельной строке) — ответы на запросы. Примеры Ввод 1 4 5 1 5 2 5 3 5 4 Вывод 1 3 2 4 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	14.06.2020, 21:47
	Тут, где-то в пределах страницы, лежит пост с такой же задачей и решением. 0

@little_Ganter 0 / 0 / 0 Регистрация: 28.06.2021 Сообщений: 12
	15.07.2021, 12:45
	TWTwoFace, ты решил проблему? я просто в той же ситуации 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	15.07.2021, 16:12
	Программа слишком долго выполнялась Добавлено через 1 час 0 минут Программа слишком долго выполнялась 0

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	15.07.2021, 16:15
	Для предложенного Вами условия: "1≤t≤105 2≤p≤109" выполняться не будет долго. А для: "1≤t≤10^5 2≤p≤10^9" нужно другое решение. 0