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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 12: Строка 12:
== Вычисление степеней, превышающих размер long long ==
== Вычисление степеней, превышающих размер long long ==


binPow(x, p, mod) == binPow(x, p % phi(mod), mod), где phi — функция Эйлера.
Если x и mod взаимно просты, то binPow(x, p, mod) == binPow(x, p % phi(mod), mod), где phi — функция Эйлера.
 
Если x и mod не взаимно просты, но p &ge; log<sub>2</sub>(mod), то binPow(x, p, mod) == binPow(x, p % phi(mod) + phi(mod), mod).


  long long phi(long long n) {
  long long phi(long long n) {
Строка 26: Строка 28:
         res -= res / n;
         res -= res / n;
     return res;
     return res;
}
== Возведение в степень матриц ==
const long long MOD = 1e9 + 7;
using Matrix = vector<vector<long long>>;
Matrix identityMatrix(int size) {
    Matrix res(size, vector<long long>(size));
    for (int i = 0; i < res.size(); i++)
        res[i][i] = 1;
    return res;
}
Matrix operator * (const Matrix &a, const Matrix &b) {
    Matrix res(a.size(), vector<long long>(b[0].size()));
    for (int y = 0; y < res.size(); y++)
        for (int x = 0; x < res[0].size(); x++)
            for (int i = 0; i < a[0].size(); i++)
                res[y][x] = (res[y][x] + a[y][i] * b[i][x] % MOD) % MOD;
    return res;
}
Matrix pow(const Matrix &m, long long p) {
    if (!p)
        return identityMatrix(m.size());
    if (p % 2)
        return pow(m, p - 1) * m;
    Matrix r = pow(m, p / 2);
    return r * r;
  }
  }



Текущая версия от 16:09, 17 сентября 2023

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

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 ≥ log2(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;
}

Возведение в степень матриц

const long long MOD = 1e9 + 7;

using Matrix = vector<vector<long long>>;

Matrix identityMatrix(int size) {
    Matrix res(size, vector<long long>(size));
    for (int i = 0; i < res.size(); i++)
        res[i][i] = 1;
    return res;
}

Matrix operator * (const Matrix &a, const Matrix &b) {
    Matrix res(a.size(), vector<long long>(b[0].size()));
    for (int y = 0; y < res.size(); y++)
        for (int x = 0; x < res[0].size(); x++)
            for (int i = 0; i < a[0].size(); i++)
                res[y][x] = (res[y][x] + a[y][i] * b[i][x] % MOD) % MOD;
    return res;
}

Matrix pow(const Matrix &m, long long p) {
    if (!p)
        return identityMatrix(m.size());
    if (p % 2)
        return pow(m, p - 1) * m;
    Matrix r = pow(m, p / 2);
    return r * r;
}

Ссылки