幂模算法

幂模就是求 a^b%m 的问题,a、b、m都是整数,a和b可能很大,a^b会超过整数表示范围,而m在整数范围内的数。

首先我们知道 x * y % m = (x % m) * (y % m) % m(证明略,设x=p_1 m+q_1, y =p_2 m+q_2很容易证明)

这意味着我们可以在计算 a ^ b 的过程中对中间值进行模m操作从而缩小中间值,而这不会影响最终结果。

然后我们可以把指数b分解成二进制,以次算出a^1, a^2, a^4, a^8,… 当b的二进制从最低位算第k位是1的时候,我们就的结果就应该乘入a^(1<<k)。

1
2
3
4
5
6
7
8
9
10
11
12
//思想a^13=a^(1+4+8)=a^1*a^4*a^8
int modExp(int a,int b,int m) {
int t=1,y=a%m;
while(b){
if(b&1){
t=t*y%m;
}
y=y*y%m;
b=(b>>1);
}
return t;
}

这就是快速幂模算法。

我们进一步,如果a更大,本身就超出了int范围,我们用string类型存储,如何快速求出a^b%m呢?

其实很简单,我们可以用一个循环把a转换成整数

1
2
3
4
int r = 0;
for(int i=0;i<a.size();i++) {
r = r * 10 + (a[i]-'0');
}

这个结果当然会导致r超过int表示范围,但是我们在过程的中间值就进行模m操作就可以了

1
2
3
4
5
6
7
8
9
10
11
12
int str2int(const string& a, int m) {
int r = 0;
for(int i=0;i<a.size();i++) {
r = (r * 10 + (a[i]-'0')) % m;
}
return r;
}

int modExp(const string& a, int b, int m) {
return modExp(str2int(a, m), b, m);
}

在进一步,如果b也更大,本身就超出了int范围,我们用string类型存储,如何快速求出 a^b%m呢?

很自然我们会想能否把b像a一样也在转成int的同时处理成b%m呢?答案是否定的。我们可以用反证法证明:

设上述问题可以先把b处理成b%m,即 a^b%ma^(b%m)%m 相等,易推得 a^m%m=1,因为这里a,b,m都是任取的,所以我们只要找到一个反例不满足 a^m%m=1就可以推得矛盾,我们可以找2^3%3 = 2 != 3,证毕。

实际上我们可以先把b处理成 b%\phi(m) ,其中phi是欧拉函数,phi(m)等于1~m中和m互质的数的个数,我会另开文章讨论欧拉函数,在此先另辟蹊径解决此问题。

\begin{align} &~~~~~a ^ b\\ &= a^{b_0*10^{n-1}+b_1*10^{n-2}+...+b_{n-1}*10^0}, 其中n=len(b), b_i是b的左起第i位数字\\ &= a^{b_0*10^{n-1}}*a^{b_1*10^{n-2}}*...*a^{b_{n-1}*10^0}\\ &= (a^{10^{n-1}})^{b_0}*(a^{10^{n-2}})^{b_1}*...*(a^{10^0})^{b_{n-1}} \end{align}

其中

a10k=(a10k1)10a^{10^k} = (a ^ {10^{k-1}})^{10}

这样我们就可以倒序遍历b的每位,并在过程中用上式维护a(10k)

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
int modExp(int a,int b,int m) {
int t=1,y=a%m;
while(b){
if(b&1){
t=t*y%m;
}
y=y*y%m;
b=(b>>1);
}
return t;
}

int str2int(const string& a, int m) {
int r = 0;
for(int i=0;i<a.size();i++) {
r = (r * 10 + (a[i]-'0')) % m;
}
return r;
}

int modExp(const string& a, const string& b, int m) {
int r = 1;
int a10k = str2int(a, m);
for(int i=b.size()-1;i>=0;i--) {
r = r * modExp(a10k, b[i]-'0', m) % m;
a10k = modExp(a10k, 10, m);
}
return r;
}

还要注意的一点是,m虽然限定在int范围内,但是如果m*m超出了int,则计算过程中的乘法可能会超出int,为了防止溢出我们可以把数据类型换成long long,并且可以用模加来实现模乘来降低溢出的可能。

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
ll modMul(ll a,ll b,ll m) {
ll t=0;
a=(a%m+m)%m;
b=(b%m+m)%m;
while(b){
if(b&1){
t=(t+a)%m;
}
a=(a+a)%m;
b>>=1;
}
return t;
}

ll modExp(ll a,ll b,ll m) {
ll t=1,y=a%m;
while(b){
if(b&1){
t=modMul(t,y,m);
}
y=modMul(y,y,m);
b=(b>>1);
}
return t;
}