数论（五）—— 快速幂

43 阅读 0 评论 29 点赞

我是靠谱客的博主寒冷蓝天，最近开发中收集的这篇文章主要介绍数论（五）—— 快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快速幂用于快速求出 a^k mod p 的结果（时间复杂度O(logk)，其中 1 ≤ a,p,k ≤ 10⁹）
如果不用快速幂的话，就得循环做 a * a 共 k 次，如果 k = 1e9，那么就要乘10⁹次，时间复杂度就太高了，所以我们要用快速幂解决此类问题。
原理
1）先预处理这些值：a^2⁰ mod p，a^2¹ mod p，a^2² mod p … … a^{2^logk} mod p
2）组合出a^K也就是把k拆成2⁰,2¹…若干个2的次幂之和
a^k = a^{2^x₁}·a^{2^x₂}·… · a^{2^x_t} = a^{2^x₁+^{2^x₂}+…+^{2^x_t}}
3）把k换算成二进制表示
如 (k)₁₀ = (110110)₂
k = 2¹ + 2² + 2⁴ + 2⁵
举个简单的例子
在这里插入图片描述
模板

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
// a^k % p
int qmi(int a,int k,int p)
{
int res = 1;
while(k)
{
//k的二进制表示中，末位是1
if(k & 1) res = (LL)res * a % p;
k >>= 1; // k的二进制右移一位
a = (LL)a * a % p; // a不断平方进行更新 
}
return res;
}

应用
快速幂求逆元
乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b⁻¹(mod m)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^m−2 即为 b 的乘法逆元。
求解方法
1）已知，a/b≡a×x(mod m)

2）两边同乘 b 得，a ≡ a× b × x(mod m)

3）又因为 b 与 m互质，那么 a 一定也与 m 互质，所以，左右两边可以消掉 a，得到 1 ≡ b × x(mod m)

4）即，b × x ≡ 1(mod m)，b × b^-1 ≡ 1(mod m),简单地说，求逆元就是找到一个x，使其满足式子：b × x ≡ 1(mod m)

5）由费马小定理得知，当 m 为质数时，有 b^(m-1) ≡ 1(mod m)

6）将 b 拆开，b * b^(m-2) = 1(mod m)

7）对比 4）和 5），可知，x = b^(m-2)

所以，求 b模m 的逆元即为求b^(m-2)

b^(m-2)我们可以借助快速幂来求。
当 b 与 m 不互质时无解，题中已知 m 为质数，那么 b 是 m 的倍数时，b×x也一定时m的倍数，mod m 等于 0 ，此时无解，即b%m == 0 时无解。
例
给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1 之间的逆元。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
// a^k % p
int qmi(int a,int k,int p)
{
int res = 1;
while(k)
{
//k的二进制表示中，末位是1
if(k & 1) res = (LL)res * a % p;
k >>= 1; // k的二进制右移一位
a = (LL)a * a % p; // a不断平方进行更新 
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
while(n -- )
{
int a,p;
scanf("%d %d",&a,&p);
int res = qmi(a,p-2,p);
if(a % p != 0) printf("%dn",res);
else puts("impossible");
}
return 0;
}