Быстрое возведение в степень: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
| Строка 30: | Строка 30: | ||
== Ссылки == | == Ссылки == | ||
* [http://e-maxx.ru/algo/binary_pow E-maxx — Бинарное возведение в степень] | * [http://e-maxx.ru/algo/binary_pow E-maxx — Бинарное возведение в степень] | ||
* [https://cp-algorithms.com/algebra/binary-exp.html cp-algorithms.com — Binary Exponentiation] | |||
* [https://cp-algorithms.com/algebra/phi-function.html#application cp-algorithms.com — Euler's totient function application in Euler's theorem] | |||
* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел] | * [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел] | ||
* [http://codeforces.com/blog/entry/43225 Codeforces — Cool tricks using Matrix Exponential] | * [http://codeforces.com/blog/entry/43225 Codeforces — Cool tricks using Matrix Exponential] | ||
Версия от 06:50, 6 января 2022
Базовая реализация
long long binPow(long long x, long long p, long long mod) {
if (!p)
return 1;
if (p % 2)
return binPow(x, p - 1, mod) * x % mod;
long long r = binPow(x, p / 2, mod);
return r * r % mod;
}
Вычисление степеней, превышающих размер long long
binPow(x, p, mod) == binPow(x, p % phi(mod), mod), где phi — функция Эйлера.
long long phi(long long n) {
long long res = n;
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) {
while (n % d == 0)
n /= d;
res -= res / d;
}
}
if (n > 1)
res -= res / n;
return res;
}
Ссылки
- E-maxx — Бинарное возведение в степень
- cp-algorithms.com — Binary Exponentiation
- cp-algorithms.com — Euler's totient function application in Euler's theorem
- algorithmica.org — Теория чисел
- Codeforces — Cool tricks using Matrix Exponential
- Habr — Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
- Habr — Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень