信息学竞赛模板（一）— 快速幂

2021-01-27 · 66次阅读 · 原创 · 数据结构与算法

1.基本形式

注意是否有取模操作，可参考例题 AcWing-89-a^b

int quick_pow(int a, int n) {
    int s = 1;
    while (n) {
        if (n & 1) s *= a;
        a *= a;
        n >>= 1;
    }
    return s;
}

2.变形

2.1 累乘变累加

来源：AcWing-90-64位整数乘法

题目要求：求 a 乘 b 对 p 取模的值。1 ≤ a,b,p ≤ $10^{18}$

说明：将快速幂的累乘变为了累加

#include<iostream>

using namespace std;
typedef unsigned long long ull;

int main() {
    ull a, b, p;
    cin >> a >> b >> p;
    ull res = 0;

    while (b) {
        if (b & 1) res = (res + a) % p;
        b >>= 1;
        a = a * 2 % p;
    }

    cout << res << endl;

    return 0;
}

2.2 数的幂变为矩阵的幂

即为矩阵快速幂，可参照详细介绍矩阵快速幂

以下代码为使用矩阵快速幂求斐波那契数列。

#include <iostream>
#include <cstring>

#define Max_rank 3
#define mod 1000000007

struct Matrix {
    long long a[Max_rank][Max_rank];

    Matrix() {
        memset(a, 0, sizeof(a));
    }

    void init() {    //每种情况的初始矩阵不同，以实际情况进行初始化
        a[1][1] = a[1][2] = a[2][1] = 1;
        a[2][2] = 0;
    }

    Matrix operator*(const Matrix b) {    //运算符重载，矩阵乘法
        Matrix res;
        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                for (int u = 1; u <= 2; u++)
                    res.a[i][j] = (res.a[i][j] + a[i][u] * b.a[u][j]) % mod;
        return res;
    }
};

long long q_pow(long long n) {
    Matrix ans, base;
    ans.init();
    base.init();
    while (n > 0) {
        if (n & 1) ans = ans * base;
        base = base * base;
        n >>= 1;
    }
    return ans.a[1][1];
}

int main() {
    long long n;
    while (std::cin >> n) {
        std::cout << q_pow(n - 2) << std::endl;
    }
    return 0;
}

标题：	信息学竞赛模板（一）— 快速幂
链接：	https://www.fightingok.cn/detail/35
更新：	2022-09-18 22:33:08
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可

信息学竞赛模板（一）— 快速幂

1.基本形式

2.变形

2.1 累乘变累加

2.2 数的幂变为矩阵的幂

Cyan