Быстрое возведение в степень: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
== Базовая реализация ==
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;
}
== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/binary_pow E-maxx — Бинарное возведение в степень]
* [http://e-maxx.ru/algo/binary_pow E-maxx — Бинарное возведение в степень]

Версия от 06:40, 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;
}

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Быстрое_возведение_в_степень&oldid=2753