【笔记】快速幂

2021zjhs005 · 2024-01-26 09:50:46 · 算法·理论

我们不妨先来看一道例题了解一下快速幂：

【模板】快速幂

~~A template.~~

观察到数据，a,b\le 2^{31}，普通的乘法是肯定不行的。

因此考虑优化：快速幂。

什么是快速幂？

顾名思义，就是快速地求出幂（a^b）。

怎么快速地求出幂？

将 a^b 展开，可得：

a^b = \underbrace{a\times a\times a\ldots\times a}_{b}

下面的 b 表示个数啦。

然后将相邻两项合并，得到：

a^b = \underbrace{a^2\times a^2\times a^2\ldots\times a^2}_{\frac{b}{2}}

这是会消除 \frac{b}{2} 个 a，因此还有 \frac{b}{2} 个 a。

但是 b 可能是奇数，所以需要额外乘一个 a，得到：

a^b = a\times \underbrace{a^2\times a^2\times a^2\ldots\times a^2}_{\frac{b}{2}}

因此，每次操作都会让 b\to \frac{b}{2}，所以时间复杂度为 \mathcal O(\log{b})，足以通过此题。

如果说 b\le 10^{10000}，那就没办法了，得用更高深的算法（本蒟蒻也不会，qwq）。

代码实现

喜欢用函数的，可以定个 quickpow(a,b)。

特判 a=0 的情况，直接返回 0。
- 其实还有一种情况，就是 b=0，但是任何数的 0 次方都等于 1，因此不用顾虑。
当 n > 0 才做，用一个 while() 循环。
- 如果 n\bmod 2 =1（是奇数），那么 ans 处理多下的一个 a，也就是 ans\gets ans\times a。
- 然后 a\gets a^2，b\gets \frac{b}{2}，这就不用解释了吧。
最后返回 ans 即可。

code

#define ll long long
inline ll quick_pow(ll a,ll b) {
    if(!a) return 0;
    ll ans=1;
    while(b){
        if(b&1)//位运算优化。
            ans=ans*a;
        a=a*a;
        b>>=1;//位运算优化 * 2。
    }
    return ans;
}

但这样并不能通过此题，因为 a^b 很有可能溢出。

那么就在上面的代码取模一下就行啦：

\boxed{AC\ code}\ \ 局部

#define ll long long
inline ll quick_pow(ll a,ll b,ll p) {
    if(!a) return 0;
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

P10035 「FAOI-R2」Paint (A)

首先打出模拟代码找规律（别的大佬都是证明，就我找规律）。

i 从 1~10 的 answer：

1
4
13
40
121
364
1093
3280
9841
29524

咦，奇怪了，这好像哪里见过，不就是小学奥数的一道经典找规律吗？

递推公式：f_i = f_{i-1} \times 3+1；

通项公式：f_i = (3^i - 1)\div 2。

求 3^i 次方不就是快速幂吗？

但是除法没有同余性质，所以需要求逆元。不知道逆元的，建议去这里。

代码就简单了：

ll quick_pow(ll x,ll p){//快速幂模板。
    ll res=x,ans=1; 
    while(p){
        if(p&1) ans=ans*res%MOD;
        res=res*res%MOD;
        p>>=1;
    }
    return ans; 
}
int main(){
    cin>>T;
    sum=quick_pow(2,MOD-2);//求逆元。
    while(T--){
        cin>>n;
        ssum=quick_pow(3,n);
        ssum=(ssum-1+MOD)%MOD;
        cout<<ssum*sum%MOD<<endl;
    }
    return 0;
}

但好像费马小定理有一个条件，不过似乎数据都是 \gcd(a,p) =1 (doge。

好啦，就到这里吧。