快速幂运算详解

简介

快速幂很重要哦，当幂是 $longlong$long long级别时（这也要用latex我是不是疯了 ），用快速幂可以将复杂度降到log级别。快速幂的重要应用就是求逆元啦（我只知道这个），下面简单介绍一下求逆元的原理。
由费马小定理：
$a^{p-1}\equiv 1\left(modp\right)$ap−1≡ 1 (mod  p) ( $p$p是素数且 $(a,p)=1$(a,p)=1)
于是就有
$a^{p-2}\equiv a^{-1}\left(modp\right)$ap−2≡ a−1 (mod  p)
然后快速幂就可以求 $amodp意义下的逆元a^{-1}$a mod p 意义下的逆元a−1了(当然 $p$ p 要是素数）

好了进入正题

怎么求 $a=b^p\left(modk\right)$a=b p (mod  k)呢？
既然复杂度是log级别了，自然是把p拆成二进制啦,其实就是处理出 $b^1,b^2,b^4,b^8,b^{16}...$b1,b2,b4,b8,b16...,然后找机会相乘一下就得了

举个例子

要求 $3^5,p=5,p=2^2+2^0$35, p=5, p=22+20, 也就是求 $3^{2^0+2^2}$320+22,即是 $3^1\ast 3^4,$31∗34, $p$  p用二进制表示成 $101$101，我们从最右边开始扫，每次右移一位，遇到第 $x$ x 位为 $1$ 1 的时候就乘上 $b^{2^x}$ b2x, 至于 $b^{2^x}$ b2x,每次右移的时候让 $b$ b 乘自己就可以了。
在这个例子中
$ans=1,b=3^1=3,此时p第0位为1，于是ans=ans\ast b,ans=3,b=3\ast 3=3^2=9$ans=1,b=31=3,此时p第0位为1，于是ans=ans∗b, ans=3,b=3∗3=32=9;
$ans=3,b=3^2=9,此时p第1位为0，ans=3,b=9\ast 9=3^4=81$ans=3,b=32=9,此时p第1位为0，ans=3,b=9∗9=34=81
$ans=3,b=3^4=81,此时p第2位为1，ans=ans\ast b,ans=243$ans=3,b=34=81,此时p第2位为1，ans=ans∗b, ans=243
懂吧，因为 $5=1+4$5=1+4，我们处理得到了 $3^1,3^2,3^4,3^8...$31,32,34,38...，该相乘的时候相乘就行了。
下面贴代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define LL long long
using namespace std;
LL ksm(LL b, LL p, LL k){
	LL s = 1;
	while(p){
		if(p & 1) s = s * b % k;
		b = b * b % k;
		p >>= 1;
	}
	return s % k;
}
int main(){
	int i, j, n, m;
	LL b, p, k;
	scanf("%lld%lld%lld", &b, &p, &k);
	printf("%lld^%lld mod %lld=%lld", b, p, k, ksm(b, p, k));
	return 0;
}