[学习笔记]快速幂&&快速乘

时间:2021-09-22 15:32:07

本质:二进制拆分(你说倍增我也没脾气)。然后是一个配凑。

合起来就是边二进制拆分,边配凑。

快速乘(其实龟速):把乘数二进制拆分。利用乘法分配率。

用途:防止爆long long

代码:

ll qk(ll x,ll y,ll mod){
ll ret=;
while(y){
if(y&) (ret+=x)%=mod;
(x+=x)%=mod;
y>>=;
}
return ret;
}

如果为了卡常,可以写成这样:

ll qk(ll x,ll y,ll mod){
ll ret=;
x%=mod;y%=mod;
while(y){
if(y&) ret=ret+x>=mod?ret+x-mod:ret+x;
x=x+x>=mod?x+x-mod:x+x;
y>>=;
}
return ret;
}

第一行必须有x%=mod,y%=mod,否则开始x,y可能很大,减一次mod不能减到mod以下。

还是错过几次。。。

(有时候卡这个取模还是挺有效的。)

快速幂(真的快速):把指数二进制拆分。利用:a^(x+y)=a^x*a^y

用途:各种指数运算,一般还取模。

推广:矩阵快速幂。

代码略。

快速幂经常与快速乘结合。log^2n也是可以接受的。

例题:

随机数生成器

直接推式子,然后分治求等比数列,爆long long,要快速乘。

复杂度:O(log^3n)

upda:2018.10.12

你以为快速幂就这么简单???
其实可以更有趣一些。

与其说快速幂本质是二进制拆分,不如说是进制拆分。

因为,我们可以10进制快速幂!!!

应用于高精快速幂。

因为/2是O(len)的,除法复杂度太高 。

而如果高精用10进制存储,可以10进制快速幂!!每次干掉低位,类比于二进制下的左移和右移。

复杂度也是logn的。奇技淫巧第24条。

快速幂快吗?很快。但是还是logn的。

如果要多次进行快速幂,那么每次logn的复杂度可能还是不能接受。

我们根据拆分的思想,如果指数在1e9范围内,那么A^k=A^([k/1e4]*1e4+k%1e4)=A^([k/1e4]*1e4)*A^(k%1e4)

可以尝试根号预处理。

[六省联考2017]相逢是问候——欧拉公式+线段树

upda:2019.1.19

延伸一下

分块预处理,可以称之为“光速幂”

然后块速递推