快速幂

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

前言

在算法程序设计竞赛中，我们竞赛选手会经常碰到对某个数N进行求大数次幂并对1e9+7取模的运算的题目，一方面求大数次幂是一个时间复杂度很高的运算（容易超时），另一方面对1e9+7取模，暗示着结果是连long long都存不下（同余定理），所以这时候快速幂取模算法就派上用场了。

同余定理

这里我们不证明了 \[ (a+b)\%c=(a\%c + b\%c)\%c \]

\[ (a*b)\%c = (a \% c)*(b \% c) \%c \]

\[ (a^b)\%c = (a\%c)^b \%c \]

快速幂取模

原理

首先假设我们有 \[ a^b\%c \] 这里(1<=a,b<=1e5,c=1e9+7),要求算出它的结果，如果我们按照正常的手段去算的话，结果肯定会超时或者溢出，所以我们可以先把式子展开：

  1. 把b转换为二进制串
  2. 根据同余定理算 这里我们用一个例子来说明，已知

\[ 2^{10}=1024, 10_{(10)} = 1010_{(2)} \]

\[ 2^{(10)}=2^{0*2^0+1*2^1+0*2^2+1*2^3} \]

\[ 2^{(10)}=2^{0*2^0}*2^{1*2^1}*2^{0*2^2}*2*{1*2^3} \]

\[ 2^{(10)}=1*2^{1*2^1}*1*2^{1*2^3} \]

\[ 2^{(10)}=1*2^2*1*2^8 \]

观察第二条推导式可知从左往右第二项数起每一项的指数都是前一项的平方倍，所以在用代码实现的时候，我们对指数（二进制）按位平方略过为指数为0的项，大大降低了时间复杂度（0较多的前提下）。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
long long quick_mod(long long a,long long b)
{
    long long ans = 1;
    a %= Mod; //对刚进来的a进行取模运算，避免后面第一次求平方运算溢出
    while(b)
    {
        if(b&1) //对二进制下的 b 进行按位与1运算，求二进制下 b 的最低位是否为1
            ans = ans * a % Mod; //对结果进行保存
        b>>=1; //二进制下的 b 右移一位，相当于十进制下的 b 除以2
        a = a * a % Mod; 
    }
    return ans % Mod;
}

p1226快速幂

b,p,k,k为长整型

输出b^p mod k = s

输入
2 10 9
输出
2^10 mod 9=7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
ll b,p,k;

ll quick_mod(ll x,ll y)
{
    ll ans=1;
    x %= k;
    while(y){
        if(y&1){
            ans = ans*x%k;
        }
        y>>=1;
        x=x*x%k;
    }
    return ans%k;
}
int main()
{
    cin>>b>>p>>k;
    printf("%lld^%lld mod %lld=%lld\n",b,p,k,quick_mod(b, p));
    return 0;
}