Быстрое возведение в степень

Базовая реализация

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

Если x и mod взаимно просты, то binPow(x, p, mod) == binPow(x, p % phi(mod), mod), где phi — функция Эйлера.

Если x и mod не взаимно просты, но p ≥ log₂(mod), то binPow(x, p, mod) == binPow(x, p % phi(mod) + phi(mod), mod).

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 — Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень