2021年2月1日更新非递归式快速幂

一些题外话

• 期末，考完了。
• 期末考，完了。

奇怪的博客又增加了

这篇博客我前两个星期就想写了，可是因为期末考种种原因现在才写。

正片开始

rt,这个问题相信暴力写法大家都会，一个for的事。

注：n,m均为已赋值正整数（因为基本没有题目考其他奇奇怪怪的数，至少我没做过，欢迎给出题目（不要私题），我会给出完善），这里以int型举例。

int ans=1;
for(int i=1;i<=m;i++) ans*=n; 

另一种暴力做法是pow

pow是个库函数，在头文件cmath中

$n^m$:pow(n,m);

注意：$pow$的返回值是double类

蛋是，

• 暴力跑for不够快，遇到卡时间的题会$\color{black}TLE$。
• pow的速度我不知道，但有一个很大的问题：不够实用

因为不能边乘边%.

很多题目都会有这样的要求，

例题：

P3414

P1226

广告：P3414我有写题解，如果不明白可以康康，记得点赞哦（光速逃

注意，以下为本文重点！！

快速幂

使暴力的for $O(m)$，变为$O(logm)$的神奇东西。

关键是还很实用。

代码

int FP(int n,int m)
{
    if(m == 0) return 1;//除0之外，任何数的0次方都等于1
    if(!m%2) return FP(m/2)%mod*FP(m/2)%mod;//将指数除以二相乘
    return n%mod*FP(m-1)%mod;//奇数指数减一
}

考虑优化以上写法（其实已经够快了），发现当指数为偶数时，我们重复算了两次FP(m/2)，于是我们可以用一个变量将它记忆下来。

int FP(int n,int m)
{
    if(m == 0) return 1;//除0之外，任何数的0次方都等于1
    if(!m%2)
    {
        int t=FP(m/2)%mod;
        return t*t%mod;//将指数除以二相乘
    }
    return n%mod*FP(m-1)%mod;//奇数指数减一
}

2021.2.1新增内容

那又有人问，我觉得递归太慢了怎么办呢？

就你会卡常是吧，就你叫卡常是吧。

实际上递归和非递归的复杂度都是$O(logn)$的，但是卡常小能手们是不会放过任何一个可以卡常的地方的。

直接放代码

inline int fp(ll a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod; b>>=1;
    }
    return res;
}

正确性显然，在此不做证明。读者们可以联想关于二进制和位运算自证。

学校老师最近突然开始赶进度，我意识到如果不写这个老师就讲了可能一些萌新（虽然我也是）需要这个，于是写了这篇文章。

写博客不易，如果觉得作者写得好，讲的清楚或对您有所启发，就请您点个赞再走吧QwQ。

Thank you for your reading!

英语不好，之前都写Thank you for your watching!，但好像应该是$reading$，有哪位大佬可以指导一下吗？