Loading...

数论小结

check评论:0 条 remove_red_eye浏览量:177 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-08-10

$gcd$

显然$gcd(a,b)=gcd(b\%a,a)$

$exgcd$

解$ax+by= gcd(a,b)$

因为$gcd(b\%a,a)=gcd(a,b)$

$(b-(b/a)*a)x+ay=ax+by$

$bx-(b/a)*ax+ay=ax+by$

$y=x,x=a-(b/a)*a$

然后递归求解即可

$crt$

$x\equiv b_i \pmod {m_i}$

令$M=\prod m_i$

对于每一个$t_i \frac{M}{m_i}\equiv 1\pmod{m_i}$

$x=\sum b_i t_i \frac{M}{m_i}$

然后最小答案是$(x\%M+M)\%M$

$excrt$

令前$k-1$个答案为$ans_{k-1}$,$M_{k-1}=\prod\limits_{i=1}^{k-1} b_i$

那么对于第$k$个式子,我们要求$ans_{k-1}+t\times M_{k-1}\equiv a_k \pmod{b_k}$

即$t\times M_{k-1}+p\times b_k = a_k-ans_{k-1}$,$exgcd$求解即可

$bsgs$

对于$a^x\equiv b \pmod p$

设$x=im-j$

则$a^{im} \equiv ba^j\pmod p$

枚举$a^{im}$和$a^j$,因为$j < m$,枚举复杂度为$\frac{p}{m}+m$,根据均值不等式$\frac{p}{m}+m \geq 2\sqrt{p}$,当且仅当$m=\sqrt p$时,取得最优

所以总复杂度$O(\sqrt p)$

扩展欧拉定理

$[1]$ 当$gcd(a,p)=1$时,$a^b\equiv a^{b\% \varphi(p)} \pmod p$

$[2]$ 当$b \ge \varphi(p) $时,$a^b\equiv a^{b\% \varphi(p)+\varphi(p)}\pmod p$

$[3]$ 否则$a^b\equiv a^b\pmod p$

chevron_left 珂朵莉树笔记
洛谷P1402 酒店之王 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名