快速幂---学习笔记

暑假准备搞学习笔记，这是第一次，看起来的效果估计很差，之后的每日一题会一直写的，加油！

问题：

快速求出来a的k次方mod P的结果，在O（log k）的时间范围内求出结果

a,p,k数据范围都在1到10的九次方内

核心思路：反复平方法

预处理+二进制转换

首先预处理，mod p, mod p,一直到 mod p总共logk个数值

目标是把a的k次方看成是之前预处理的各个数字的乘积

关键还是把 k 二进制化， 将 k 进行二进制表示

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL) res * a % p;//对k取地址，看最后一位，是1就乘上a
        k >>= 1;//去掉最后一位，再进行判断
        a = (LL) a * a % p;//a变为下一个，即最后的平方
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    while(n -- )
    {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a,k,p));
    }
    return 0;
}