Loading...

欧拉扩展定理及莫比乌斯反演

check评论:0 条 remove_red_eye浏览量:410 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-12

欧拉定理:

$a^{ϕ(n)}$ $\equiv 1$ $\pmod n$

欧拉扩展定理:

$a^b \equiv$ $a^{b \% ϕ(p)}$ -> $gcd(a,p)=1$ $\pmod p$

$a^b \equiv$ $a^{b}$ -> $gcd(a,p)\ne 1,b<ϕ(p)$ $\pmod p$

$a^b \equiv$ $a^{b \% ϕ(p)+ϕ(p)}$ -> $gcd(a,p)\ne 1,b\ge ϕ(p)$ $\pmod p$

莫比乌斯反演:

$F(n)=\sum_{d|n} f(d)$ -> $f(n)=\sum_{d|n}\mu (d)F(\frac{n}{d})$

$F(n)=\sum_{d|n} f(d)$ -> $f(n)=\sum_{d|n}\mu (\frac{d}{n})F(d)$

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名