快速幂

洛谷 P1226 【模板】快速幂||取余运算

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll quickpow(ll a, ll b, ll p = 10) {
    // 计算a的b次方
    if (b == 0) return 1;
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

ll a, b, p;

int main() {
    cin >> a >> b >> p;
    ll ans = quickpow(a, b, p);
    printf("%lld^%lld mod %lld=%lld",a,b,p,ans);
    return 0;
}

这个快速幂其实就是把一个$ a^b $转换成了$(b_{1} * a^{1}) * (b_{2} *a^{2}) * (b_{3} *a^{3}) * (b_{4} *a^{4}) ...... (b_{n} * a^{n})$. 其中$b_n...b_2b_1b_0$是$b$的二进制表示. 这样可以减少乘法运算的次数, 复杂度更低. (还有一种二分法的快速幂， 个人觉得代码没这个简单)

ll quickpow(ll a, ll b, ll p = 10) {
    // 计算a的b次方
    if (b == 0) return 1; // 首先如果b是0的话直接返回1就行
    int ans = 1; // ans用来存结果
    while (b) {
        if (b & 1) { // 取出b二进制中的最后一位, 如果是1的话就进行乘法
            ans = ans * a % p; 
        }
        a = a * a % p; // 算出下次运算要乘的a
        b >>= 1; // 把b按位右移
    }
    return ans;
}

这里实现了一个计算 a 的 n 次幂的函数 quick_pow，其中用到了位运算。需要注意的是，n 的类型和取模的值 MOD 都需要根据实际情况进行选择。如果需要计算大数的幂次运算，可以使用高精度算法。