幂模算法

幂模就是求 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)。

//思想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转换成整数

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

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

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%m 和 a^(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}

其中

$$a^{10^k} = (a ^ {10^{k-1}})^{10}$$

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

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，并且可以用模加来实现模乘来降低溢出的可能。

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;
}