12317. Поле по
модулю
Для заданных целых чисел a, b, c, n, p найдите значение выражения:
Результат выведите в виде двух
чисел x и y таких что
Вход. Пять целых чисел a, b,
c, n, p. Известно, что:
·
p – простое число,
·
0 ≤ a, b
< p,
·
1
≤ c < p,
·
0 ≤ n ≤
1018
Выход. Выведите два целых числа x
и y – коэффициенты при 1 и 
соответственно, по модулю p.
|
Пример входа 1 |
Пример выхода 1 |
|
2 1 5 2 17 |
9 4 |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
3 2 5 10 17 |
1 2 |
РЕШЕНИЕ
комбинаторика
Анализ алгоритма
Вычисления следует выполнять в расширенном поле:
Правила операций:
·
Сложение
·
Умножение
После определения операции
умножения элементы поля 
можно возводить в степень стандартным методом
быстрого возведения в степень за время O(log2n). Это позволит вычислить .
Пример
В первом примере
= 
= 
Рассмотрим
второй пример:
Пусть x = 
. Вычислим его
степени:
x2 = 
= 
= 
x4 = 
= 
= 
x8 = 
= 
= 
Теперь можно
вычислить результат:
x10 = x8 ∙ x2 =
=
(168 + 
+ 
+ 360) 
= 1 + 
Реализация алгоритма
Объявим
структуру Num для хранения
числа вида 
.
struct Num
{
long long x, y; // x + y*sqrt(c)
};
Реализуем умножение в поле . Функция mult возвращает
произведение чисел a и b.
Num mult(Num& a, Num& b)
{
Num res;
res.x = (a.x * b.x + c * a.y % p * b.y) % p;
res.y = (a.x * b.y + a.y * b.x) % p;
return res;
}
Функция pow реализует возведение в степень basen, где base – число в поле .
Num pow(Num base, long long n)
{
Num res = { 1, 0 }; // единица поля
while (n > 0)
{
if (n & 1)
res
= mult(res, base);
base = mult(base, base);
n >>= 1;
}
return res;
}
Основная часть программы. Читаем входные данные.
scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n,
&p);
Инициализируем начальное число start = 
.
Num start = { a % p, b % p };
Вычисляем и выводим ответ ans = startn mod p
= .
Num ans = pow(start, n);
printf("%lld %lld\n", ans.x, ans.y);