算法模板：数论之快速幂

文档中心

算法模板：数论之快速幂

前言
快速幂
算法模板
- 快速幂求逆元
完结散花
参考文献

前言

唤我沈七就好啦。

快速幂

$给你三个整数 a,k,p，求 a^{k} mod p$

数据范围
1≤n≤10⁵
1≤ai,pi≤2∗10⁹

思路

将指数转化成二进制

只需要在指数的二进制为 1 时与底数的幂次方相成即可

底数的幂次方是在不断自乘的中生成的

实现方法

每次判断指数二进制末尾是否是 1。

如果是就更新答案 ans = ans * a % p 之后 k >> 1。

底数自乘 a = a * a % p 。

例如： k=11，二进制下是 k=1011 。
$b（二进制）的最后一位是 1 吗？是的。这代表 a^{11} = a^8 × a^2 × a^1 中的 a^1 存在。$
这时答案 ans = ans * a % p ， a = a^1 之后 a 累乘 a = a * a % p ;

之后在通过 k>>=1 的操作将 k 二进制的第二位数移到最后一位，再次判断是否 1。

ans = ans * a % p ，此时的 a = a ^ 2 % p，a 继续累乘 a = a * a % p ;

直到判断到第 3 位时发现并不为 1 ，这是 ans 不更新，a 继续累乘 .

重复上述操作 ans = ans * a % p ,此时 a = a ^ 8 % p;
$a^{11} = a^8 × a^2 × a^1$

算法模板

typedef long long LL;LL power(LL a,LL k,LL p){LL ans=1;while(k){if(k&1)ans=ans*a%p;k>>=1;a=a*a%p;}return ans;}

快速幂求逆元

给定 n 组 a i,p i，其中 p i 是质数，求 a i 模 p i

的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 0∼p−1

之间的逆元。

乘法逆元的定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(modm)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b m−2 即为 b 的乘法逆元

人话：

x 满足 b * x = 1 %（n）则称 x 为 b 的逆元

即 b乘其逆元的积%上一个给定的数等于 1

当n为质数时，结合费马定理，可以用快速幂求逆元：

a / b ≡ a * x (mod n)
两边同乘b可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)

由费马小定理可知，当n为质数时

b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当n为质数时，b的乘法逆元 x = b ^ (n - 2)

#includeusing namespace std;const int N = 1e6+10;typedef long long LL;int a,b;int hh,tt=-1; LL power(LL a,LL k,int p){LL ans=1;while(k){if(k&1)ans=ans*a%p;k>>=1;a=a*a%p;}return ans;}int main(){int n,m,p;cin>>n;while(n--){cin>>a>>p;if(a%p==0)printf("impossible\n");elsecout<<power(a,p-2,p)<<"\n";}return 0;}

完结散花

ok以上就是对算法模板：数论之快速幂的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。

参考文献

https://www.acwing.com/activity/content/19/

算法模板：数论之快速幂