第四章快速幂

一：快速幂

• 首先 a * b mod c，当a很大的时候，可以提前用a mod c一下，一样的。

快速幂是什么？
快速求出下面式子的取余。

• 具体基本原理，预处理logk个数，把a^k拆分，k变成二进制

• 如何计算预处理的值？

每个预处理的值是上一个值的平方然后mod p

#include <iostream>
using namespace std;
typedef long long LL; // 10 ^ 9相乘超过int
int qmi(int a, int k, int q)
{
    int res = 1; //初始相乘保证不影响整个过程
    while (k)
    {
        if (k & 1) res = (LL)res * a % q; // k&1一个目的是检查初始值1是特殊情况，还有就是检查k的二进制，倒数第某位是不是1，是就乘，上面图的方式，分解的样子相乘
        k >>= 1; // 右移，后面凑出那个预先值，右移以后最后一位是1，代表k分解的二进制中，这一位是1，上面一行就要相乘并且取余
        a = (LL)a * a % q; // 凑出那个预先的值
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--)
    {
        int a, k , q;
        cin >> a >> k >> q;
        cout << qmi(a, k, q) << endl;
    }
    return 0;
}