简单数论的常见trick

文章中$[...]$为艾佛森括号，$(x,y)$为$gcd(x,y)$的缩写。

1.素数的分布密度约为$\frac{1}{\ln n}$

2.${\lim }_{n\to \infty }\frac{\pi (n)\times \ln n}{n}=1$

3.${\sum }_{i=1}^n\frac{1}{i}=n\ln n$

4.${\sum }_{i\in [1,n]}\frac{1}{p}=\ln \ln n$

5.$a\equiv b$ mod $m$, $a\equiv b$ (mod $n$),则$a\equiv b$ mod $[a,b]$

6.$(k,m)=d,ka\equiv k{a}^{\prime }$ (mod $m$),则$a\equiv a^{\prime }$(mod $m$)

7.关于exgcd通解问题

我们可以简单知道所求的$x_0,y_0$是一组特殊解而没有任何的特殊性质（雾）

希望求得某些边缘解和通解来计算

考虑通解$y=y_0\pm w$的构造：

明显$y=((a,b)-a{x}_0)/b\pm aw/b$，而想要求得整数通解，那么$aw/b$必为整数。

若$(a,b)=1$，那么$w_{min}=b$，若$(a,b)̸=1$那么有$a=p{q}_1,b=p{q}_2$，$(q_1,q_2)=1$。

此时$w_{min}=q_2$，即$b/(a,b)$，于是求得通解$y=y_0+\frac{b}{(a,b)}\times t$

同理可以得到$x$的通解$x=x_0+\frac{b}{(a,b)}\times t$,最小正整数解即为$x_{min}=x_0\mathrm{m}\mathrm{o}\mathrm{d}\frac{b}{(a,b)}$

设$k=\frac{b}{(a,b)}$，因为$x$可能$\le 0$，所以实际的$x_{min}$为$(x_{min}\mathrm{m}\mathrm{o}\mathrm{d}k)+k$

8.证明${\sum }_{d|n}\varphi (d)=n$

证明1： $$n=\sum _{d=1}^n\sum _{i=1}^n[(i,n)=d]=\sum _{d|n}\sum _{i=1}^{n/d}[(i,\frac{n}{d})=1]=\sum _{d|n}\varphi (\frac{n}{d})=\sum _{d|n}\varphi (d)$$

正确性：第一步转化中每个数只会被算一次，所以是$n$

证明2：

$F(n)={\sum }_{d|n}\varphi (d)$是$id$和$\varphi$的卷积，因此是积性函数

直接套唯一分解定理，变成求$F({\prod }_i{p}_i^{k_i})$，把不同的质因子分开，变成求${\sum }_{i}F(p_i^{k_i})$

对于每个$F(p_i^{k_i})$，实际上是等比数列求和+1，求得$F(p_i^{k_i})=p_i^{k_i}$

因此$F(n)=n$

证明3：

$$\begin{array}{rl}\varphi (n)& =\sum _{i=1}^n[(i,n)=1]\\ & =\sum _{i=1}^n\sum _{e|(i,n)}\mu (e)\\ & =\sum _{i=1}^n\sum _{e|n}\sum _{e|i}\mu (e)\\ & =\sum _{e|n}\sum _{i=1}^n\sum _{e|i}\mu (e)\\ & =\sum _{e|n}\mu (e)\frac{n}{e}\\ & =id\ast \mu \end{array}$$ 因此 $$\varphi (n)=id\ast \mu (n)$$ 两边同时卷$1$ $$\varphi \ast 1=id\ast ϵ$$ 即 $$\sum _{d|n}\varphi (d)=n$$

9.扩展欧拉定理 $(a,m)≠1,a^{(c\mathrm{m}\mathrm{o}\mathrm{d}\varphi (m))+\varphi (m)}\equiv a^c$

主要用于底数$a$和模数$m$不互质的情况。

先考虑证明质数的幂次$p^c,c\ge \varphi (m)$适用于此定理。

$m<p$明显$(p,m)=1$，故成立

因为$p$是质数且$(p,m)≠1$，所以当$m>p$的时候$m$一定是$p$的倍数，得到 $m=t\times p^r,(t,p)=1$，$\varphi (t)|\varphi (m)$

所以$p^{\varphi (t)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}t$

$(t,p)=1$意味着$\varphi (m)=\varphi (t)\varphi (p^r)$，即$p^{\varphi (m)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}m$

指数同改变$r$即得到$p^{\varphi (m)+r}\equiv p^r$

$p^c\equiv p^{c-r+r}\equiv p^{\varphi (m)+r}\equiv p^r$，明显$p^r$在意义上与$p^c$相同，因此$p^c\equiv p^{c\mathrm{m}\mathrm{o}\mathrm{d}\varphi (m)}$

对于一个数$s={\prod }_i{p}_i^{k_i}$，因为$\forall i,j,(p_i,p_j)=1$,所以$\varphi (s)=\varphi ({\prod }_i{p}_i^{k_i})$

明显直接乘起来就好

10.关于bsgs

问题是求$y^x\equiv z\mathrm{m}\mathrm{o}\mathrm{d}p$，正常情况下是$(y,p)=1$，然后解法是对指数分块

先特判。

1.$z=1$的时候$x=0$

2.$y=0$的时候$z≠0$无解，$z=0,x=1$

3.$z=0$

变成$y^x\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}p$，明显$p=t\times y^r,(t,y)=1$

设分块大小是$B$，变成$y^{iB}\equiv z{y}^j$

因为复杂度是$\max (\frac{p}{B},B)$，所以明显$B$取$\sqrt{p}$，然后右边插到hash表里去左边枚举系数然后查一下。

注意，因为$y^k$在$\mathrm{m}\mathrm{o}\mathrm{d}p$意义下$(注意(y,p)=1)$最多只有$\varphi (p)$，最坏情况下即$p-1$个，所以$B$取$\sqrt{p}$直接下取整即可。

如果$(y,p)≠1$的话$y$明显没逆元，所以就先搞成互质的情况

sbcsdn吞了我保存的公式，是傻逼吗？ 不想写exbsgs了，算了还是补上吧（愤恨）

$A^x\equiv B\mathrm{m}\mathrm{o}\mathrm{d}C$

循环对$C$和$A$做除法,定义$R={\prod }_i{d}_i,d_i=(\frac{C}{{\prod }_j^{i-1}{d}_j},A)$

最后变成$\frac{A^k}{R}\times A^{n-k}\equiv \frac{B}{R}\mathrm{m}\mathrm{o}\mathrm{d}\frac{C}{R}$，这个时候$(\frac{A^k}{R},\frac{C}{R})=1$，$(A^{n-k},\frac{C}{R})=1$，存在逆，直接当成普通的bsgs做就好