C/C++

Задача на С++

Обратное число
В этой задаче нужно ответить на 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
ВИ
Виталик Иванов
77
☺
Мирзоев Бахтиёр
Мирзоев Бахтиёр
514
Лучший ответ
Виталик Иванов через нейросетку похоже, неверно
Модульная арифметика:
 a * b mod p = 1

    a mod p = a

Если a = 1, то b = 1
Иначе смотрим, сколько раз нужно перепрыгнуть через p:
 b1 = p div a + 1
(p является простым, поэтому никогда не делится на a > 1)
 r1 = a * b1 mod p = a * b1 - p = a * (p div a) + a - p =

   = p - p mod a + a - p = a - p mod a

(0 < r1 < a, т.к. a > p mod a > 0)

Если r1 = 1, то b = b1

Иначе, если (a - 1) mod (a - r1) = 0, то b = b1 * (a - 1) div (a  - r1)
Если ни одно условие не выполнено, то повторяем шаг:
 b2 = p div r1 + 1

r2 = r1 - p mod r1

(0 < r2 < r1, т.к. r1 > p mod r1 > 0)

Если r2 = 1, то b = b1 * b2

Иначе, если (a - 1) mod (a - r2) = 0, то b = b1 * b2 * (a - 1) div (a - r2)
Иначе, переходим к следующим bi, ri. Поскольку каждое следующее r меньше предыдущего, но больше 0, рано или поздно придём к 1 (а ветка с делимостью a - 1 помогает "срезать угол", когда видим целое число оставшихся итераций).

Теперь реализуем это в программе:
 #include 



using namespace std;



int main() {

    unsigned t;

    cin >> t;

    while (t-- != 0) {

        unsigned long p, a;

        cin >> p >> a;

        unsigned long b = a == 1 ? 1 : p / a + 1;

        unsigned long r = a - p % a;

        while (r > 1 && (a - 1) % (r - 1) != 0) {

            b *= p / r + 1;

            r -= p % r;

        }

        cout
Сергей Артюхов
Сергей Артюхов
54 053
Вы можете использовать алгоритм расширенного алгоритма Евклида для нахождения обратного числа по модулю. Вот пример кода на C++, который решает эту задачу:
 #include  

using namespace std; 

int t, p, a; 

int x, y; 

int gcd(int a, int b) { 

    if (b == 0) { 

        x = 1; 

        y = 0; 

        return a; 

    } 

    int d = gcd(b, a % b); 

    int temp = x; 

    x = y; 

    y = temp - (a / b) * y; 

    return d; 

} 

int main() { 

    cin >> t; 

    while (t--) { 

        cin >> p >> a; 

        gcd(a, p); 

        cout
АБ
Артем Бейсюк
25 860

Похожие вопросы