Loading...

随便写的一些东西

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

$Cipolla$算法求二次剩余

不妨设$b^2-a$是模$p$意义下的二次非剩余,则$x\equiv (b+\sqrt{w})^\frac{p+1}{2}\pmod p$为 方程的解

因为$w$是模$p$意义下的二次非剩余,因此$w^{\frac{p-1}{2}}\equiv -1\pmod p$

结合二项式定理,则$(b+\sqrt w)^p\equiv b^p+\sqrt {w}^p\equiv b-\sqrt w \pmod p$

故上式必定是$x^2\equiv a$的一组解,由拉格朗日定理,$x$为整数,时间复杂度$O(log\ p)$

数论函数的生成函数一般定义为$F=\sum\limits_{i=0}^{+\infty} f^i(p) x^i$

令$F$为$I$函数的生成函数,易得$F=\frac{1}{1-x}$
令$G$为$id$函数的生成函数,则$G=1+px+p^2x^2+p^3x^3+...+p^wx^w$

则$G-G*px=1$

故$G=\frac{1}{1-px}$

令$E$为$\varepsilon$的生成函数,则$E=1$

令$M$为$\mu$的生成函数,因为对于一个质数$p$只有指数为$0$时$\mu=1$,指数为$1$时$\mu=-1$,显然$M=1-x$

然后可以发现$M*F=E$,即$\sum\limits_{d|n} mu(d) =[n=1]$

令$\Phi$为$\varphi$的生成函数,显然指数为$0$时$\varphi=1$,指数为$1$时$\varphi=p-1$,指数为$w(w>1)$时$\varphi=p^{w-1} (p-1)$

则$\Phi=1+(p-1)x+p(p-1)x^2+p^2(p-1)x^3+...+p^w(p-1)x^{w+1}$

则$px*\Phi-\Phi=x-1$

则$(px-1)\Phi=x-1$

$\Phi=\frac{1-x}{1-px}$

显然$\Phi * F =G$,我们就得到了$\sum\limits_{d|n} \varphi(d)=n$

chevron_left HDU5909 Tree Cutting
[转]轨道计数 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名