Как посчитать a^b mod m, когда b — гигантская башня степеней (теорема Эйлера для показателя)?
Нужно посчитать a^b mod m, но b само задано как огромное число (или вообще как a^{a^{...}} — башня степеней), которое не влезает ни в какой тип. Бинарное возведение требует b как число. Как сократить показатель? Слышал, что помогает теорема Эйлера.
2 ответа
Идея — сократить показатель по модулю φ(m), а не возводить честно. Если gcd(a, m) = 1, то по теореме Эйлера a^{φ(m)} ≡ 1 (mod m), поэтому:
a^b ≡ a^{b mod φ(m)} (mod m)
Значит, если b дано строкой/большим числом, сначала вычисли b mod φ(m) (например, проходя по цифрам строки), а потом обычное бинарное возведение за O(log).
Но если gcd(a, m) ≠ 1, простую формулу применять нельзя — есть обобщённая (поднятый показатель / lifting the exponent для модуля): при b ≥ log2(m)
a^b ≡ a^{(b mod φ(m)) + φ(m)} (mod m)
// b задано строкой; возвращает a^b mod m
long long power_tower(long long a, const string& b, long long m) {
long long phi = euler_phi(m);
long long e = 0; bool big = false;
for (char c : b) { // e = b mod phi, заодно отмечаем b >= phi
e = e * 10 + (c - '0');
if (e >= phi) { big = true; e %= phi; }
}
if (big) e += phi; // обобщённая теорема Эйлера
return binpow(a, e, m);
}
Сложность — O(len(b) + log m). Для башни степеней применяй это рекурсивно: показатель верхнего этажа считается по модулю φ(m), следующий — по φ(φ(m)) и т.д. (последовательность φ быстро доходит до 1).
Грабля с обобщённой формулой: + φ(m) нужно добавлять только если b ≥ φ(m) (точнее, b ≥ log2 m). Если b маленькое — считай напрямую a^b, без сокращения, иначе получишь неверный ответ. Поэтому в коде и держим флаг big. Для башен степеней a^{a^{a^{...}}} рекурсия по уровням и спуск по φ(φ(...)) сходится за O(log m) уровней, потому что φ уменьшает аргумент минимум вдвое за два шага.