题解：P1226 【模板】快速幂

题目大意

在

2\le a,b \le2^{31}

、

2\le p \le2^{31}

的限制下计算

a^b\mod p

的结果。

大体思路

由于

a

和

b

都很大，

O(b)

的暴力相乘肯定会超时，我们需要想出

O(\log b)

的做法来处理幂运算。

我们首先要知道一个小学知识：

a^b\times a^c=a^{b+c}

；

(a^b)^c=a^{(b\times c)}

。

类似于倍增的二进制拆位思路，我们把

a^b

可以拆成由若干个

a^{(2^n)}

相乘组成的式子，这样我们就能把复杂度降到

O(\log b)

。

拆的办法也很显然，把

b

拆成由若干个由

2^n

组成的式子，然后再将这几个

a^{2^x}

乘起来。

就如样例的例子，

2^{10}

：

10=2^3+2^1

。

所以：

2^{10}=2^{2^3}\times 2^{2^1}

。

部分代码讲解

CPP

int ans=1;
while(b) {
  if(b%2==1) {
    ans=ans*a%p;
  }
  b/=2;
  a=a*a%p;
}

我们对

b

进行处理，如果其不可以被二整除，那么我们就先把

a^b

拆成

a^{b-1}\times a

，用变量

ans

记录这些被分出来的

a

，可以被二整除或处理完后，我们将

b

除以二，将

a^b

拆为

a^{b/2}\times a^{b/2}

，我们这里让当前的

a

变为

a^2

即可，之后的处理保留这次的平方。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long a,b,p;
	cin>>a>>b>>p;
	cout<<a<<"^"<<b<<" mod "<<p<<"=";
	int ans=1;
	while(b) {
		if(b%2==1) {
			ans=ans*a%p;
		}
		b/=2;
		a=a*a%p;
	}
	cout<<ans;
	return 0;
}

最后给大家一个考试时用的模板，作为自定义函数使用：

CPP

long long ksm(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}

题解：P1226 【模板】快速幂

文章操作

题目大意

大体思路

部分代码讲解

Code

相关推荐

评论

题解：P1226 【模板】快速幂