快速幂

问题

求出$a^b\mod c$的值，其中a，b，c是整数，且$0<a,c<10^9$，$0<b<10^{18}$

算法设计

暴力算法

考虑用循环直接求出$a^b$的值，最后对$c$取模。

long long ans=1;
for (long long i=1;i<=b;i++)
{
    ans*=a;
}
ans%=c;

这个代码其实有两个缺陷。

1. 时间复杂度为$O(b)$，即要进行$10^{18}$次运算，一般情况下计算机在1s内无法完成。
2. ans会超过long long范围。

下面对其进行优化。我们来看看取模的性质:

$(a*b)\mod c=((a\mod c)*(b\mod c))\mod c$

所以我们可以在每一次乘$a$的时候都对$c$取模，即

ans*=a;
ans%=c;

这样我们就解决了缺陷2。但是时间复杂度并没有优化，还有没有别的办法呢？

快速幂算法

我们首先考虑一下手算$3^{10}$，$3^{10}=(3^2)^5=9^5=9*9^4=9*81^2=9*(81^2)^1$，很容易发现规律。而且，这个算法时间复杂度为$O(log_2b)$，时间大大减少。

typedef long long ll;
ll fast_pow(ll a,ll b,ll c)
{
    ll ans=1;
    a%=c;
    while (b)//不能写成b>1，否则会出问题！！！
    {
        if (b%2==1)//可以用b&1进行更快的判断
        {
            ans=(ans*a)%c;
        }
        a=(a*a)%c;
        b/=2;//可以用b>>=1来代替
    }
    return ans;
}

补充：费马小定理

若$p$为素数，$a$为正整数，且$p，a$互质。则有$a^{p-1}=1\mod p$。