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

数学(二)

快速幂

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),接着再看更方便。

相关小说

穿成电竞文里的菜鸡小炮灰 连载中
穿成电竞文里的菜鸡小炮灰
哒布吉呀
#年度MVP选手林宿雨穿书了#(双男主)(文中三观不代表作者三观,真的真的真的!)1林宿雨在带领自家俱乐部取得中国赛区的冠军,还没有享受冠军......
9.4万字7个月前
漂亮的女人 连载中
漂亮的女人
飞向天宏
某夏天,漂亮的女人与闺蜜去海滩晒太阳,享受着阳光紫外线美身,结果从南方卷起了超强龙卷风……一场意外,成就她们的美梦!
8.0万字6个月前
无声陪伴 连载中
无声陪伴
184***446_9133823268
十七年的陪伴最后却无能为力
0.1万字5个月前
空吟史,暮寻录 连载中
空吟史,暮寻录
晶小运
“天赋真的有那么重要吗?”介绍:卿文锦(主人公)农村出生,偶然间去登最高山长月山,生性倔强,却没有灵根,靠着前面神仙登山挡风,跟到屁股后面,......
3.0万字5个月前
Selita国度的英雄们 连载中
Selita国度的英雄们
死蟒食骸
【龙偶】【自设世界观】曾经,存在着一个神奇而古老的国度,名为Selita。在这个国度里,居住着各色各样的龙,它们是这片土地的真正主宰。其中,......
0.6万字4个月前
噬梦游戏:虚实 连载中
噬梦游戏:虚实
梦十八灯
这,究竟是不是一场梦?
1.1万字3个月前