快速幂+取模

前言

从今天开始好好学数学orz


目录

  • 快速幂运算
  • 取模运算
    • 大整数取模
    • 大整数乘法取模
    • 幂取模

快速幂运算

如果我们要计算ana^n的值,正常情况下需要将aa乘以自身nn次,而这种暴力的计算方法需要花费O(n)O(n)的时间。利用二分思想,快速幂运算算法能够将这种幂运算的时间复杂度降低至O(logn)O(\log n),从而大大提高计算速率。

对于ana^n,如果我们采用a×a××ana\underbrace{a\times a\times\cdots\times a}_{n个a}的方式进行计算的话,我们需要进行nn次乘法运算。如果我们采用分治的思想,每次将幂指数除以2(为了发现规律,我们先假设nn为2的幂次方,这样每次都能刚好整除):

  • an=an2an2a^n=a^\frac{n}{2}\cdot a^\frac{n}{2}
  • an=an4an4an2a^n=a^\frac{n}{4}\cdot a^\frac{n}{4}\cdot a^\frac{n}{2}
  • an=aaa2a4an4an2log2n+1a^n=\underbrace{a\cdot a\cdot a^2\cdot a^4\cdots a^\frac{n}{4}\cdot a^\frac{n}{2}}_{\log_2 n + 1项}

可见,如果我们能在O(1)O(1)的时间内计算出每一项的值,那么我们只需要进行log2n+1log_2 n +1次乘法运算,就能够得到最终的结果。而对于每一项而言,它的值都可以通过由前一项进行平方计算得到,因此,在O(1)O(1)的时间内计算出每一项的值是可行的。

于是我们得到了一个时间复杂度为O(logn)O(\log n)的计算ana^n的值的算法。(nn为2的幂次方)

那么对于一般的ana^n呢?我们再观察一下刚刚得到的式子:

  • an=aaa2a4an4an2log2n+1=a20+20+21+22++2log2n1a^n=\underbrace{a\cdot a\cdot a^2\cdot a^4\cdots a^\frac{n}{4}\cdot a^\frac{n}{2}}_{\log_2 n + 1项}=a^{2^0+2^0+2^1+2^2+\cdots+2^{\log_2 n -1}}

aa的指数部分20+20+21+22++2log2n12^0+2^0+2^1+2^2+\cdots+2^{\log_2 n -1}很自然地让我们联想到十进制数的二进制表达,它们有着相似的形式。我们知道,任意的正整数nn都能被表示成为若干个2的幂的和(十进制数能够被转化为二进制数),因此,对于一般的ana^n,我们只需要将nn表示为若干个2的幂的和,就可以将ana^n表示为上述式子,从而以O(logn)O(\log n)的时间复杂度计算ana^n

即:令n=m020+m121+m222++mlog2n2log2nlog2n+1mi{0,1}n=\underbrace{m_02^0+m_12^1+m_22^2+\cdots+m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}}_{\lfloor\log_2 n\rfloor+1项},m_i\in\{0,1\},则an=am020am121amlog2n2log2na^n=a^{m_02^0}\cdot a^{m_12^1}\cdots a^{m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}},其中ai+1=ai2a_{i+1}=a_i^2

这就得到了快速幂运算算法。

下面给出一种非递归的C语言实现:

1
2
3
4
5
6
7
8
9
10
11
12
long long fpow(long long a, long long n)
{
long long ans = 1;
while (n)
{
if (n & 1)
ans *= a;
a *= a;
n >>= 1;
}
return ans;
}

aa开始,如果nn的二进制数末位不为零(即对应上式mim_i不为零),则将该数乘入结果变量中,然后将aa进行平方,移动到mi+1m_{i+1},重复进行判断。可见,我们需要进行log2n+1\lfloor\log_2 n\rfloor+1次乘法运算与平方运算,故时间复杂度为O(logn)O(\log n)


取模运算

大整数取模

一般情况下,如果某个题目的答案是一个超过long long存储范围的大整数,大部分题目并不会要求直接输出该大整数作为答案,而是要求输出这个大整数对某个数取模的结果。

输入正整数nnmm,输出nmodmn\bmod m的值。n10100m109n\leq10^{100},m\leq10^9。

在开始之前,我们需要知道一些模运算的基本性质:

  • (a+b)modn=((amodn)+(bmodn))modn(a+b)\bmod n=((a\bmod n)+(b\bmod n))\bmod n
  • (ab)modn=((amodn)(bmodn))modn(a-b)\bmod n=((a\bmod n)-(b\bmod n))\bmod n
  • abmodn=(amodn)(bmodn)modnab\bmod n=(a\bmod n)(b\bmod n)\bmod n

可以看到,两个数相加/相减/相乘之后再对某一个数取模,等于各个数对这个数分别取模再相加/相减/相乘的结果对这个数取模。值得注意的是,如果各个数对这个数分别取模再相加/相减/相乘的结果小于这个数的话,则最后的取余是不必要的。
即:

  • amodm+bmodm<ma\bmod m+b\bmod m<m,则有:(a+b)modn=amodn+bmodn(a+b)\bmod n=a\bmod n+b\bmod n
  • amodmbmodm<ma\bmod m-b\bmod m<m,则有:(ab)modn=amodnbmodn(a-b)\bmod n=a\mod n-b\mod n
  • (amodm)(bmodm)<m(a\bmod m)(b\bmod m)<m,则有:abmodn=(amodn)(bmodn)ab\bmod n=(a\bmod n)(b\bmod n)

那么,对于一个两位数x=10a+bx=10a+b,由上面的基本性质我们可以进行以下推导:

  1. xmodm=(10a+b)modmx\bmod m=(10a+b)\bmod m
  2. a=km+rxmodm=(10km+10r+b)modma=km+r,则x\bmod m=(10km+10r+b)\bmod m
  3. (10km+10r+b)modm=(10kmmodm)+(10r+b)modm=(10r+b)modm(10km+10r+b)\bmod m=(10km\bmod m)+(10r+b)\bmod m=(10r+b)\bmod m
  4. r=amodmxmodm=(10×(amodm)+b)modm\because r=a\bmod m,\therefore x\bmod m=(10\times (a\bmod m)+b)\bmod m

有了这样一个式子,我们就可以对大整数nn(假定为1234)进行取模了:

  1. 将大整数nn分解为“自左向右”的形式:1234=((1×10+2)×10+3)×10+41234=((1\times 10+2)\times 10+3)\times 10+4
  2. 对于每一个10a+b10a+b型的括号,采用(10×(amodm)+b)modm(10\times (a\bmod m)+b)\bmod m的方式进行取模
1
2
3
4
5
6
7
int bmod(char *num, int len, int m)
{
int ans = 0;
for (int i = 0; i < len; i++)
ans = (int)((1ll * ans * 10 + num[i] - '0') % m);
return ans;
}

算法的时间复杂度随正整数的位数线性增长。

大整数乘法取模

计算a×bmodma,bm1018a\times b\bmod m,a,b\le m\le 10^{18}

对于这一类型的取模,我们当然可以使用高精度计算得到a×ba\times b的结果,再通过大整数取模方法进行计算。不过,我们还有更为高效的做法。

由模运算的基本性质,我们知道,取模运算可以通过将大数拆分为一个个小的模块分别取模再处理来简化运算。然而,如果对a,ba,b分别取模再相乘,其结果仍然可能溢出。因此,我们不妨先从拆分a×ba\times b入手。

我们可以借鉴快速幂运算中的思想,将其中一个乘数表示为若干个2的整数次幂的和的形式:

  • a=m020+m121+m222++mlog2n2log2nmi{0,1}a=m_02^0+m_12^1+m_22^2+\cdots+m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor},m_i\in\{0,1\}
  • a×b=m020×b+m121×b+m222×b++mlog2n2log2n×ba\times b=m_02^0\times b+m_12^1\times b+m_22^2\times b+\cdots+m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}\times b

这样,两个大整数的相乘计算就转化为了相加计算,我们可以在相加的过程中进行取模运算,从而能够防止在计算过程数据溢出。

1
2
3
4
5
6
7
8
9
10
11
12
long long multimod(long long a, long long b, long long m)
{
long long ans = 0;
while (a)
{
if (a & 1)
ans = (ans += b) % m;
b = (b <<= 1) % m;
a >>= 1;
}
return ans;
}

与快速幂运算类似,第ii项表达式的值可以由第i1i-1项表达式乘以2得到。因此,我们需要进行log2n+1\lfloor\log_2 n\rfloor+1次加法操作。故该算法的时间复杂度为O(logn)O(\log n)

幂取模

我们常常会遇到这样的问题:

计算xnmodmx^n\bmod m

由模运算的基本性质容易知道,我们只需要在相乘的过程进行取模运算即可。使用快速幂运算算法计算xnx^n,很容易在O(logn)O(\log n)的时间内得到这一问题的解:

1
2
3
4
5
6
7
8
9
10
11
12
13
long long fpow_mod(long long x, long long n, long long m)
{
x %= m; // 预处理x,避免第一次进行平方运算时溢出
long long ans = 1;
while (n)
{
if (n & 1)
ans = ans * x % m;
x = x * x % m;
n >>= 1;
}
return ans;
}

对于mm为质数的幂取模计算,我们还可以利用费马小定理来提高算法效率。

费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有ap11modpa^{p-1}≡1(\bmod p)

xxmm互质,mm为质数,则有:

  • xn=xk(m1)+nmod(m1)modm=xk(m1)modm+xnmod(m1)modm=xnmod(m1)modmx^n=x^{k(m-1)+n\bmod (m-1)}\bmod m=x^{k(m-1)}\bmod m+x^{n\bmod(m-1)}\bmod m=x^{n\bmod(m-1)}\bmod m

在大多数题目中,mm往往等于1000000007。这是一个很特别的数:

  1. 10000000071000000007是一个质数。
  2. 1000000007×21000000007\times 2仍在int的数据范围内,换句话说,对于int型变量a,ba,b,利用模运算的基本性质计算(a+b)mod1000000007(a+b)\bmod 1000000007的过程中不会溢出。
  3. 100000000721000000007^2仍在long long的数据范围内,换句话说,对于long long型变量a,ba,b,利用模运算的基本性质计算a×bmod1000000007a\times b\bmod 1000000007的过程中不会溢出。

这简直是为费马小定理优化而生的数字呢。

文章作者: 会思考的下丘脑
文章链接: https://magicalsheep.cn/2583221088/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 小羊圈