快速幂

快速幂(拓展移位运算，二进制的理解)

求模

分治的方法

// 求：b^p
// 思路：
// 任意一个数p，可以表示成 p = 2 * p/2 + p%2
// b^(2 * p/2 + p%2)，就可以拆开后，递归调用f(p/2)，递归终止边界是p == 0, return 1;

// 求2^b
#include <iostream>
using namespace std;
int f(int b)
{
    if (b == 0) return 1;
    int t = f(b / 2);
    if (b & 1) return t * t * 2;
    else return t * t;
}
int main()
{
    int a, b;
    cin >> b;
    cout << f(b) << '\n';
    return 0;
}

// 求a^b
#include <iostream>
using namespace std;
typedef long long ll;
int f(int a, int b)
{
    if (b == 0) return 1;
    ll t = f(a, b / 2);
    if (b & 1) return t * t * a;
    else return t * t;
}
int main()
{
    int a, b;
    cin >> a >> b;
    cout << f(a, b) << '\n';
    return 0;
}

移位运算的方法

根据数学常识，每一个正整数可以唯一表示为若干个指数不重复的2的次幂的和。如果b在二进制下有k位，其中第i位的数字是，那么

于是：

因为向上取整，所以上式乘积项的数量不多于k个，
又因为

所以，通过k次递推求出每个乘积项，当时，把该乘积项累积到答案中。
b & 1 运算可以取出 b 在二进制表示下的最低位， 而 b >> 1 运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历 b 在二进制表示下的所有数字 。时间复杂度是 。

// 求 a^k mod p，时间复杂度 O(logk)
// 模板请记忆
// 写法1
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)  //当k不是0的时候
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}
// 写法2
int power(int a, int b, int p){
    int ret = 1;
    for (; b; b >>= 1){
        if (b & 1) ret = 1ll * ret * a % p;
        a = 1ll * a * a % p; 
    }
    return ret;
}

//upd20220331
int power(int a, int b, int p){
    int ret = 1;
    while (b){
        if (b & 1) ret = ret * a % p;
        b >>= 1;
        a = 1ll * a * a % p;
    }
}
// 洗牌
// https://iai.sh.cn/problem/610
// 结合倍增，ST表
// f[N][30];是预处理出来的ST表
int cur = i, b = k, t = 0;
while (b){
    if (b & 1) cur = f[cur][t];  // 第二维，就是在枚举二进制位
    t++, b >>= 1;
}

例题，取余运算（mod）

输入b，p，k的值，求 b^p mod k 的值。其中b，p，k为长整型数。

例题，2011

通过测试发现，2011的n次方的结果，每500个数一循环。1次方、501次方、1001……结果一样。
2次方，502次方，1002次方……结果一样。所以，尽管指数可能有200位，只需要考虑最后的3位指数就可以了。如果指数n不足3位，直接计算2011的n次方结果mod 10000就行了。