数学联邦政治世界观
超小超大

数学(二)

快速幂

1.快速幂求xᵇ % p

其中x,b,p均∈ [1,1e9],时间复杂度为O(logb)

算法原理:反复平方法‬

b=2ˣ¹+. . . . . .+2ˣⁿ (通过2进制数位实现),比如11的二进制为1011,1011中第零位为1,代表 2⁰ ,第一位为1,代表 2¹ ,第二位为0,代表0,第三位为1,代表 2³ ,所以11=2^0+2^1+2^3。同理, xᵇ=x²⁰×. . . . . .x²ˡᵒᵍᵇ 可快速得到。其中 x²ⁿ 通过反复平方得到。

参考代码:

LL qmi(int x, int b, int p)

{

LL res = 1 % p;

while (b)

{

if (b & 1) res = res * x % p;

x = x * (LL)x % p;

b >>= 1;

}

return res;

}

2.快速幂求x mod p的乘法逆元‬

初等数学上乘法逆元就是倒数(a*x=1,则x是a的乘法逆元),算法中我们常讨论取模运算的乘法逆元(α * xmodp ≡ 1 ,代码表示为a * x % p = 1,x是a%p的乘法逆元)

算法中常求乘法逆元将除法变成乘法以简化运算。

当n为质数时,可以用快速幂求逆元:

代码与快速幂代码相同,只不过参数改为qmi(x,p-2,p)【推导用到了费马小定理】

龟速乘

与快速幂类似,求(α * b)modp的值,a,b,p范围均[1,1e18]。

其实就是把快速幂的相乘算法改为相加算法

LL qadd(LL a, LL b, LL p)

{

LL res = 0;

while (b)

{

if (b & 1) res = (res + a) % p;

a = (a + a) % p;

b >>= 1;

}

return res;

}

数学联邦政治世界观提示您:看后求收藏(笔尖小说网http://www.bjxsw.cc),接着再看更方便。

相关小说

雁归有时 连载中
雁归有时
生命高度
本书别名《没有明天》【虐文】【已完结】结合了某某些真实事件改编、以文字的方式呈现彭萧是在家暴家庭中长大,七岁那年,父亲残忍杀害母亲,22岁,......
9.3万字8个月前
末世语阳 连载中
末世语阳
不知名刀刀
女主角酚易:一个坚强、聪明、有领导力的女性,末世前是医生。男主角白莱:一个勇敢、机智、有责任感的男性,末世前是军人。在共同的战斗和生存中,酚......
2.0万字8个月前
本文番外 连载中
本文番外
月醉星河
作品为原创.禁止抄袭.不喜勿喷.作者:幻薇梦;幻洢梦;月醉星河;幻瑰梦;幻蝶梦;幻玫梦;洢佳;喜欢蓝天白云的L;柳柳薇;蔷薇的温柔以上都是作......
110.2万字6个月前
神修大陆 连载中
神修大陆
唐朝汐
在这个神修的大陆,法术强者为王的大陆上,有无数宗门和学院,可是有这么一个宗门他们以蝶为主,以音为辅,以扇为攻,宗门里的亲生血脉者刚会有一种特......
8.0万字6个月前
巷往巷往 连载中
巷往巷往
139***084_7062947698
1.5万字5个月前
星骸之野 连载中
星骸之野
放眼有千秋
在钢铁与蒸汽交织的末日世界,五个残缺的灵魂被命运缠绕——玩世不恭的废品猎人握着斩断命运的铁剑。病弱的贵公子体内沉睡着毁灭的密码。追求完美的执......
1.7万字4周前