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

@Eisenstein · Регистрация: 28.06.2021

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int main()
{
    int t, a, p;
    cin >> t;
    int* s = new int[t];
    for (int i = 0; i < t; i++)
    {
        cin >> p >> a;
        b = 1;
        while ((a * b - 1) % p != 0)
        {
            b++;
        }
        s[i] = b;
    }
    for (int i = 0; i < t; i++)
    cout << s[i] << endl;
}

Ну и я не знаю как по-другому написать алгоритм, чтобы выполнялся за 5 сек. Помогите, пожалуйста

@LegionK · 15.07.2021, 19:43

Кликните здесь для просмотра всего текста

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
31
32
33
34
35
36
37
38
#include <iostream>
#include <cmath>
 
using namespace std;
 
#define ll long long
 
ll binpow(ll a,ll n,ll p) {
 
    if(!n)return 1;
    if(n % 2)return ((binpow(a,n-1,p) * a)%p);
    else{
 
        ll b = (binpow(a, n/2,p))%p;
 
        return ((b * b)%p);
    }
}
 
 
int main()
{
    ll z;
    cin >> z;
 
    for(ll zz = 0;zz<z;++zz){
 
        ll p,a;
        cin >> p >> a;
 
        cout << binpow(a,p-2,p) << "\n";
 
    }
 
 
 
    return 0;
}

Попробуйте.

@Eisenstein · 15.07.2021, 19:53 **[ТС]**

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
31
32
#include <iostream>
using namespace std;
 
int binpow(int a, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return binpow(a, n - 1) * a;
    else {
        int b = binpow(a, n / 2);
        return b * b;
    }
}
 
 
int main()
{
    long long t, s, y, a, p;
    cin >> t;
    int* g = new int[t];
    for (int i = 0; i < t; i++)
    {
        cin >> p >> a;
        y = binpow(a, p - 2);
        s = y % p;
        g[i] = s;
 
    }
 
    for (int i = 0; i < t; i++)
        cout << g[i] << endl;
}

Сделала недавно вот это, но на проверке пишет, что программа выдаёт неверный ответ. Что в ней не так?

Добавлено через 8 минут

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

Попробуйте.

Я не очень понимаю, как она работает. Может она и пройдёт тест, но я её не понимаю

@LegionK · 15.07.2021, 19:56

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

как она работает.

Мне это очень интересно. Давайте вы отправите и мне расскажите о результате? Я буду вам очень благодарен в любом случае.

@Eisenstein · 15.07.2021, 19:59 **[ТС]**

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

Давайте вы отправите и мне расскажите о результате?

Она прошла

@LegionK · 15.07.2021, 20:00

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

Она прошла

Спасибо вам большое.

@Eisenstein · 15.07.2021, 20:01 **[ТС]**

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

Спасибо вам большое.

Да, но мне от этого мало толку. Я то ничего почти не поняла. Но спасибо

@LegionK · 15.07.2021, 20:20

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

Я то ничего почти не поняла

Вы смогли разобраться в алгоритме бинарного возведения в степень? Того самого, код которого мы с вами скопировали с emaxx? Предположим мы хотим возвести число a в степень b. Если степень b четная, то a^b = a^(b/2) * a^(b/2). Если b нечетная, то a^b = a*a^(b-1). Где b-1 уже четное число для которого мы применим прошлый шаг. Представьте это как такую цепочку : сначала стоит b, потом стоит b-1, потом стоит (b-1)/2 и т.д и так пока не дойдет до 0. Когда a^0 = 1. Всего от b до 0 цепочка будет длины чуть меньше 2*log(2,n). Это если на каждом шаге мы сначала вычитаем единицу, а потом делим на два. То есть log(2,n) (- из определения) делений на два, столько же вычитаний.

Теперь предположим мы хотим найти не a^b, а a^b mod p. Здесь будет абсолютно то же самое, т.к

(a^b) % p = ((a^(b/2)%p) * (a^(b/2)%p)) % p

И для нечетных b : (a^b)%p = (a * (a^(b-1)%p)) % p

Можно почитать почему так вот тут - https://brestprog.by/topics/modulo/

Статья в целом полезная. Я правда очень быстро забываю после прочтения, но это не так важно. Главное запомните, что если в задаче фигурируют большие числа по модулю и алгоритм у вас в целом верный, то можете фигарить взятия по модулю везде где хочется, вообще везде. Кроме деления. Ну и при вычитании надо тоже контролировать, чтобы в отрицательное не уходило. В сложении и вычитании чем больше остатков от деления тем лучше.

Собственно то, что я написал сверху написано в виде кода в предыдущем моем сообщении.

@alexu_007 · 15.07.2021, 20:24

Может с такими знаниями не нужно никуда ехать, место чужое занимать?

@LegionK · 15.07.2021, 20:27

Не по теме:

Че-то вы, Алексей, решили основательно ребенка лет 14ти задушить. :D

@Eisenstein · 15.07.2021, 20:38 **[ТС]**

LegionK, спасибо огромное!!! Реально понятнее стала это тема

Добавлено через 1 минуту

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

Может с такими знаниями не нужно никуда ехать, место чужое занимать?

Меня и не выберут, не волнуйтесь так

. Мне всего лишь захотелось попробовать себя в программировании, это запрещено?

@alexu_007 · 15.07.2021, 20:46

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

Мне всего лишь захотелось попробовать себя в программировании, это запрещено?

Это не запрещено, но начинать нужно с того, что попроще, и постепенно переходить от простого к сложному.

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

Че-то вы, Алексей, решили основательно ребенка лет 14ти задушить.

А вы уверены, что вопрос задаёт ребёнок, 14 лет, и вообще женщина?

@LegionK · 15.07.2021, 20:51

Eisenstein, пишите.
alexu_007, конечно это ребёнок. По стилю общения видно. Аватар тоже соответствует.

Все, заканчиваем тему, что-то лишнее началось. Со своей стороны я точно здесь больше отвечать не буду.

@Eisenstein · 15.07.2021, 20:53 **[ТС]**

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

нужно с того, что попроще,

Он бесплатный и у меня профильный класс в школе, так что это в любом случае будет полезно

@alexu_007 · 15.07.2021, 22:02

Судя по тому, что было написано ранее, вы так и не поняли:

- как это работает вообще
- куда можно было "прикрутить" код, который предложил я
- почему выдал ошибку код, который написали вы по подсказке LegionK
- что поменял LegionK и почему после этого тест был пройден

Байт · 29.06.2022, 11:42

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

@Dopustim · 26.04.2023, 09:08

TheCalligrapher, Здравствуйте, помогите пожалуйста с данным вопросом https://www.cyberforum.ru/abou... st16876283

Новые блоги и статьи Все статьи Все блоги /
Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .	SUNO Ai - Река Без Дна zorxor 31.07.2026 Автор стихотворения - астрофизик Марина Катыс Ссылка на сгенерированную музыкальную композицию: https:/ / suno. com/ song/ 6f6e5464-b290-4650-be6c-44c85f8d8013 Я говорю, что Время- как вода течет. . .	Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .
Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,316
	15.07.2021, 20:24
	Может с такими знаниями не нужно никуда ехать, место чужое занимать? 0

@LegionK
	15.07.2021, 20:27
	Не по теме: Че-то вы, Алексей, решили основательно ребенка лет 14ти задушить. :D 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	15.07.2021, 20:51
	Eisenstein, пишите. alexu_007, конечно это ребёнок. По стилю общения видно. Аватар тоже соответствует. Все, заканчиваем тему, что-то лишнее началось. Со своей стороны я точно здесь больше отвечать не буду. 0

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,316
	15.07.2021, 22:02
	Судя по тому, что было написано ранее, вы так и не поняли: - как это работает вообще - куда можно было "прикрутить" код, который предложил я - почему выдал ошибку код, который написали вы по подсказке LegionK - что поменял LegionK и почему после этого тест был пройден 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	29.06.2022, 11:42
	Вот еще на ту же тему Оптимизировать код (Обратное число) 0

@Dopustim 3 / 3 / 0 Регистрация: 07.04.2023 Сообщений: 30
	26.04.2023, 09:08
	TheCalligrapher, Здравствуйте, помогите пожалуйста с данным вопросом https://www.cyberforum.ru/abou... st16876283 0

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

Решение