【acwing】算法指南蓝书_位运算_a^b_64位整数乘法

位运算_a^b 快速幂纯模板

穿越隧道

将b(十进制）转化为二进制的形式：如b=5，即101.
用乘法来实现乘方。

#include <iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
void quick(ll a, ll b, ll p){
    ll res = 1 % p;
    while(b){
        if(b&1){
            res = (1ll) * res % p * a % p;
        }
        a = a % p * a % p;
        b >>= 1;
    }
    cout << res % p << endl;
}
int main(){
    cin >> a >> b >> p;
    quick(a,b,p);
    return 0;
}

64位整数乘法

穿越隧道

这道题和前面很像.
幂运算是res = 1，因为类似a * a * a, 除非a为0，res = 1，可以让连乘进行下去。
整数乘法是两个数a和b之间的乘法，将最小数b化为二进制，让a分别乘以b在二进制位数为1的系数，然后相加。
用加法实现乘法（龟速乘，原来两个数相乘为O(1),龟速乘为O(log)
b的二进制位有O(logb)位。
两个long long 数相加，不会爆long long
long long 最大是$$2^{63}?1=9,223,372,036,854,775,808?1$$
整数乘法相当于有b个a相加，次数是$$O(b)$$
如b = 5, b = 101

#include <iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
void qmi(ll a, ll b, ll p){
    ll res = 0 % p;
    while(b){
        if(b & 1){
            res = (1ll) *(res + a) % p; //将a * (2^2) + a * (2^0)
        }
        a = a % p * 2 % p; //实现在b的二进制位数为1的系数，如2^0, 2^2，将其与a相乘，实现了a*b
        b >>= 1;
    }
    cout << res << endl;
}
int main(){
    cin >> a;
    cin >> b;
    cin >> p;
    if(a < b){
        swap(a,b);
    }
    qmi(a,b,p);
    return 0;
}