快速幂||取余运算

首先看一道水题：快速幂取余，计算\(a^b\)%k的值，朴素的算法复杂度为O(b)，而快速幂的办法复杂度为O(log b)。

快速幂

快速幂的原理很简单，比如：我们知道\(2^6=2^3*2^3\)。

那么我们要求\(2^6\)，不就是计算\(2^3*2^3\)吗。

也就是说：当b mod 2 =0 时，\(a^b=a^\frac{b}{2}*a^\frac{b}{2}\)。

那么同理，当b mod 2 =1 时，\(a^b=a^{b-1}*a\)。
不难想到，可以用递归的方式来实现快速幂取余。
需要注意的是当k=1时，需要特判一下余数为零，因为任何整数模一都等于0。~~

递归写法

typedef long long ll;
//递归快速幂取余
ll qpow(ll a,ll b,ll m)
{
    if(b==0) return 1;
    else if(b&1) return a*qpow(a,b-1,m)%m;
    else{
        ll num=qpow(a,b/2,m)%m;
        return (num*num)%m;
    }
}

其中的 b&1 是按位与，当b为奇数时返回1，if条件成立。反之亦然。

迭代写法

如果不了解位运算可以看看 位运算

我们发现对于\(a^b\)，如果将b写为2进制，比如 6 就是 110 。于是2，1号位都为1。显然6=\(2^1 + 2^2\)。那么\(a^6=a^{2^1}*a^{2^2}\)。
那么经过推导，可以发现：

1. 初始令ans = 1,用来存放累积的结果。
2. 判断b的二进制末尾是否为1 ，（及判断 b&1 是否为 1），也可以理解为判断b 是否为奇数。如果是的话，令ans乘上a的值。
3. 令a平方，并使b右移一位，（也可以理解为，b/2）
4. 只要b 大于0，就返回 第二点。

ll qpow(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1) ans=ans*a%m;
        a=(a*a)%m;
        b>>=1;
    }
    return ans;
}

最后放下完整的开头例题的ac代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll aa,bb,k;
//递归快速幂取余
ll qpow(ll a,ll b,ll m)
{
    if(b==0) return 1;
    else if(b&1) return a*qpow(a,b-1,m)%m;
    else{
        ll num=qpow(a,b/2,m)%m;
        return (num*num)%m;
    }
}
//迭代快速幂取余
ll qpow1(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1) ans=ans*a%m;
        a=(a*a)%m;
        b>>=1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld",&aa,&bb,&k);
    if(k==1) printf("%lld^%lld mod %lld=0",aa,bb,k);
    else printf("%lld^%lld mod %lld=%lld",aa,bb,k,qpow1(aa,bb,k));
    return 0;
}