9627. a^b^c
Вычислите
значение
(mod 109 +
7)
Вход. Первая строка содержит количество тестов n. Каждая из следующих n
строк содержит три числа a, b, c (a, b, c ≤ 109).
Выход. Для каждого теста выведите в отдельной строке (mod 109 +
7).
|
Пример
входа |
Пример
выхода |
|
3 3 7 1 15 2 2 3 4 5 |
2187 50625 763327764 |
РЕШЕНИЕ
степень
Анализ алгоритма
По малой теореме
Ферма ap – 1 = 1 (mod p), где p простое. Число p = 109 + 7 простое. Отсюда например следует что a(p – 1) * l = 1 (mod p) для любого l.
Для вычисления выражения a^b^c сначала следует
найти k = bc, после чего
вычислить ak. Однако число bc большое, представим
его в виде bc = (p – 1) * l + s для некоторых l и s < p – 1. Тогда
a^(b^c) mod
p = a(p – 1) * l + s mod p = (a(p – 1) * l * as) mod p = as mod p
Очевидно что s = bc mod (p – 1). Следовательно
a^(b^c) mod
p = a^(b^c mod (p – 1)) mod p
Пример
Вычислим
выражение 3^2^3
mod 7. Модуль 7
специально выбран простым. Значение выражения равно
3^(2^3) mod 7 = 38 mod 7 = 6561 mod 7 = (937 * 7 + 2)
mod 7 = 2
Из теоремы Ферма
следует что 36 mod 7 = 1.
Следовательно для любого натурального k
(36 mod 7)k = 36k mod 7 = 1
Поскольку 2^3 = 23 = 8, то 38 mod 7 = 36 * 1 + 2 mod 7 = 32 mod 7 = 9 mod 7 = 2
Исходное
выражение также можно вычислить как
3^(2^3) mod 7 = 38 mod 7 = 38 mod 6 mod 7 = 32 mod
7 =
9 mod 7 = 2
Реализация алгоритма
Функция
powmod вычисляет значение xn 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("%d", &n);
while (n--)
{
scanf("%lld
%lld %lld", &a, &b, &c);
Вычисляем
res = bc mod (p – 1).
res = powmod(b, c,
1000000006LL);
Вычисляем
res = ares mod p.
res = powmod(a, res,
1000000007LL);
Выводим
ответ.
printf("%lld\n",
res);
}