快速幂取模

快速幂取模的算法是寒假的时候就学了的，那我为什么又在这里写呢？其实原因很简单，第一次学的时候没有很好的理解，所以又写了一遍，好了，废话不多说，开始干吧

为何有快速幂？

C语言不是有%（取模）符号么，那我们要快速幂干嘛？顾名思义，快速幂，讲究的就是一个“快”字，朴素算法中，直接计算a^b%c（对a的b次方取c的模）会导致出现一个相当麻烦的地方，就是a^b会产生一个相当大的数字，数字可能会超过C语言提供的整数范围从而导致程序错误，因此，快速幂取模应运而生，他不但可以节省空间，还能有较快的速度

快速幂的原理是什么呢？

对于取模运算，有一个公式：

(a*b)%c=(a%c)*(b%c)%c

我们可以在这个式子上稍动一些手脚，比如：

(a2)%c=(a%c)(a%c)%c=(a%c)^2 %c

将大数拆成多个数，不但可以避免出现超过范围的数，也能够让幂取模的运算更有效率

那该怎么写呢？

1.非递归：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//将long long型用ll表示
ll quickmod(ll a,ll b,ll c)
{
    int ret=1;
    //这里如果a==c要进行单独判断，否则答案会等于1
    while(b) //当b不等于0时
    {
        if(b&1) //判断是否为奇数，相当于b%2
            //2&1=0,3&1=1
            ret=ret*a%c;
        a=a*a%c;
        b>>=2; //等同于b/=2
    }
    return ret;
}
 
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    if (b==0){
        int ret=a%c;
        printf("%lld^%lld mod %lld=%d",a,b,c,ret);
    }
    else {
        int ret=quickmod(a,b,c);
        printf("%lld^%lld mod %lld=%d",a,b,c,ret);
    }
    return 0;
}

2.递归：（这里我就简写了...）

typedef long long ll;
ll binaryPow(ll a, ll b, ll m){
    if(b == 0)
        return 1;
    else if(b % 2 == 1)
        return a * binaryPow(a, b - 1, m) % m;
    else{
        ll num = binaryPow(a, b/2, m) % m;//优化 
        return num * num % m;
                // 不直接写成return binaryPow(a, b/2, m) * binaryPow(a, b/2, m)
    }
}

相关例题：【洛谷P1226】https://www.luogu.com.cn/problem/P1226