9606. Деление по модулю

Заданы три натуральных числа a, b и n. Вычислите a / b mod n. То есть найдите такое значение x что b * x = a mod n.

Вход. Три натуральных числа a, b, n (n ≤ 2 * 10⁹, 1 ≤ a, b < n). Известно, что n простое.

Выход. Выведите значение a / b mod n.

Пример входа 1	Пример выхода 1
3 4 7	6
Пример входа 2	Пример выхода 2
4 8 13	7

РЕШЕНИЕ

возведение в степень

Анализ алгоритма

Поскольку число n простое, то по малой теореме Ферма выполняется равенство b^n-1 mod n = 1 для любого b (1 ≤ b < n). Это равенство можно переписать в виде (b * b^n-2) mod n = 1, откуда следует, что обратным числом к b является y = b^n-2 mod n. Следовательно a / b mod n = a * b^-1 mod n = a * y mod n.

Обратное число можно найти, используя расширенный алгоритм Евклида. Для этого следует решить сравнение: ax = 1 (mod n). Рассмотрим диофантово уравнение

ax + ny = 1

и найдем его частичное решение (x₀, y₀) с помощью расширенного алгоритма Евклида. Взяв уравнение ax₀ + ny₀ = 1 по модулю n, получим ax₀ = 1 (mod n). В случае отрицательного значения x₀ к нему следует прибавить n. Таким образом x₀ = a^-1 (mod n) является числом, обратным к a.

Пример

Рассмотрим второй пример. Вычислим 4 / 8 mod 13. Для этого следует решить уравнение 8 * x = 4 mod 13, откуда x = (4 * 8^-1) mod 13.

Поскольку число 13 простое, то по малой теореме Ферма следует, что 8¹² mod 13 = 1 или (8 * 8¹¹) mod 13 = 1. Следовательно, 8^-1 mod 13 = 8¹¹ mod 13 = 5.

Вычисляем ответ: x = (4 * 8^-1) mod 13 = (4 * 5) mod 13 = 20 mod 13 = 7.

Реализация алгоритма

Функция powmod вычисляет значение xⁿ mod m.

long long powmod(long long x, long long n, long long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

return (x * powmod(x, n - 1, m)) % m;

}

Основная часть программы. Читаем входные данные.

scanf("%lld %lld %lld", &a, &b, &n);

Вычисляем y = b^n-2 mod n, x = a * y mod n.

y = powmod(b, n - 2, n);

x = (a * y) % n;

Выводим ответ.

printf("%lld\n", x);

Реализация алгоритма – расширенный алгоритм Евклида

#include <stdio.h>

long long a, b, n, d, x, y, inv, res;

void gcdext(long long a, long long b,

long long &d, long long &x, long long &y)

{

if (b == 0)

{

d = a; x = 1; y = 0;

return;

}

gcdext(b, a % b, d, x, y);

long long s = y;

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

x = s;

}

int main(void)

{

scanf("%lld %lld %lld", &a, &b, &n);

// b * inv + n * y = 1

gcdext(b, n, d, inv, y);

if (inv < 0) inv += n;

res = (a * inv) % n;

printf("%lld\n", res);

return 0;

}

Python реализация

Основная часть программы. Читаем входные данные.

a, b, n = map(int, input().split())

Вычисляем y = b^n-2 mod n, x = a * y mod n.

y = pow(b, n - 2, n)

x = (a * y) % n

Выводим ответ.

print(x)