快速幂

快速幂

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以O(logn)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

---

让我们先来思考一个问题：7的10次方，怎样算比较快？

方法1：最朴素的想法，77=49，497=343，… 一步一步算，共进行了9次乘法。

这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

方法2：先算7的5次方，即77777，再算它的平方，共进行了5次乘法。

但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。

方法3：先算77得49，则7的5次方为4949*7，再算它的平方，共进行了4次乘法。

模仿这样的过程，我们得到一个在O(logn) 时间内计算出幂的算法，也就是快速幂。

递归快速幂

//递归快速幂
int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

在实际问题中，题目常常会要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。

//递归快速幂（对大素数取模）
#define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
 if (n == 0)
 return 1;
 else if (n % 2 == 1)
 return qpow(a, n - 1) * a % MOD;
 else
 {
 ll temp = qpow(a, n / 2) % MOD;
 return temp * temp % MOD;
 }
}

非递归快速幂

//非递归快速幂
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

最初ans为1，然后我们一位一位算：

1010的最后一位是0，所以a^{1这一位不要。然后1010变为101，a变为a}2。

101的最后一位是1，所以a^2这一位是需要的，乘入ans。101变为10，a再自乘。

10的最后一位是0，跳过，右移，自乘。

然后1的最后一位是1，ans再乘上a^8。循环结束，返回结果。

这里的位运算符，>>是右移，表示把二进制数往右移一位，相当于/2；&是按位与，&1可以理解为取出二进制数的最后一位，相当于%2==1。这么一等价，是不是看出了递归和非递归的快速幂的关系了？虽然非递归快速幂因为牵扯到二进制理解起来稍微复杂一点，但基本思路其实和递归快速幂没有太大的出入。

以上内容摘自知乎用户Pecco南大计院大佬；

例题：

【模板】快速幂

题目描述

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

样例 #1

样例输入 #1

2 10 9

样例输出 #1

2^10 mod 9=7

提示

样例解释

$2^{10} = 1024$，$1024 \bmod 9 = 7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。

按照上面思路，代码如下：

#include <iostream>
#include <string.h>
#include <unordered_map>
#include <queue>
using namespace std;
#define int long long


signed main(void)
{
    int a,b,p;
    int cona,conb;
    cin>>a>>b>>p;
    cona=a;conb=b;
    int ans=1;
    while(b)
    {
        if(b&1)ans=(ans*a)%p;
        a=a*a%p;
        b>>=1;
    }
    printf("%lld^%lld mod %lld=%lld\n",cona,conb,p,ans);
     return 0;
}

例题2：费马小定理和线性算法的应用

【模板】模意义下的乘法逆元

题目背景

这是一道模板题

题目描述

给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。

这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

输入格式

一行两个正整数 $n,p$。

输出格式

输出 $n$ 行，第 $i$ 行表示 $i$ 在模 $p$ 下的乘法逆元。

样例 #1

样例输入 #1

10 13

样例输出 #1

1
7
9
10
8
11
2
5
3
4

提示

$ 1 \leq n \leq 3 \times 10 ^ 6$，$n < p < 20000528 $。

输入保证 $ p $ 为质数。

一、逆元的概念

单位元 和 逆元，我们在初中和高中的时候其实就已经接触到了，只不过到了大学才系统性的给他们更加官方的命名。接下来，我们首先来了解下什么是单位元，什么是逆元。

1、单位元

【定义1】在一个集合中，对于某种运算 （注意：这里代表通用运算的表示符号，并不是特指乘法），如果对于任何的集合元素 ，和元素  运算，得到还是集合元素  本身，则称  为这个运算下的单位元。

2、逆元

【定义2】在一个集合中，对于某种运算 ，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元。

先是费马小定理：

ll fpm(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
        if(power & 1) (ans *= x) %= mod;
    return ans;
}
int main() {
    ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
}

但是，这个做法会tle

于是我们用线代的知识：

inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

完整代码如下：

#include <iostream>
#include <string.h>
#include <unordered_map>
#include <queue>
using namespace std;
#define int long long
int n_e[20000528]={0};

signed main(void)
{
    int n,p;
    n_e[1]=1;
    cin>>n>>p;
    cout<<n_e[1]<<"\n";
    for(int i=2;i<=n;i++)
    {
        n_e[i]=((p-(p/i))*n_e[p%i])%p;
        cout<<n_e[i]<<"\n";
    }
     return 0;
}