数论相关算法
素数的分布
$[1,n]$有$\frac n {\ln n}$个素数
$\sum \frac 1 p_i = O(\log\log n)$（埃式筛复杂度）
GCD
$gcd(a,b) = gcd(a-b,b) = gcd(b,a\%b)$
$gcd(a,b)lcm(a,b) = ab$
类欧几里得问题
$\displaystyle \sum_{x=1}^n \lfloor \frac{ax+b}{c}\rfloor$
$a,b,c,n \leq 10^9$
实质上是$y=\frac{ax+b}{c}$下的整点个数，$a$如果小于0其实是可以$+c$的
其实我们可以默认$a < c$否则可以$a \%=c$
现在就是求一个梯形里面的整点个数。剩下的三角形就可以旋转一下坐标系，然后就变成了一个小三角形的整点个数然后问题又变成了一个$a \geq c$的问题又可以递归了。
裴蜀定理
$ax+by=c$有解当且仅当$(a,b) | c$
就是在$gcd$的过程中记录一下就好了。
素数
素性测试
暴力，$O(\sqrt n)$
欧拉定理，如果$(a,m)=1$$a^{\varphi(m)} \equiv m \quad(\bmod m)$
否则，$a^{b} \equiv a^{\min (b, b \bmod \varphi(m)+\varphi(m))}(\bmod m)$
经典例题$2^{2^{2^{…}}} \bmod p$
其实就是一直用下面那个%，%到1为止。这样做答案就是$\varphi(x)$一直进行下去，复杂度大概是$\log$
Miller Rabin
Farmat 判别法
$a^{p-1} \equiv 1 \pmod p$，所以我们每次随机一个整数$a$康康$a^{p-1}$是否等于1，如果不是说明肯定不是素数。
这样的正确率是$50\%$以上的，但是有例如 561 这种没有反例存在。
我们在求$a^{p-1}$时，让$p-1 = 2^{k}\times t$所以我们先求出$a^t$，倍增的时候，我们知道$x^2\equiv 1 \pmod p$等价于$x\equiv \pm 1 \pmod p$如果$p$是质数 。所以我们往上平方的时候看看是否等于1，如果等于1就看看上次是不是$\pm1$
Pollard-Rho
给定一个合数，怎么快速分解？
给定一个合数$n$，希望找出一个它的非平凡因子
由于生日悖论，每次在$[1,n]$随机，$O(\sqrt n )$次就大概率有两个数字相同。
我们拿出一个随机数列，$x_i = F(x_{i-1})$在$O(\sqrt n)$步就会产生一个$\rho$形的循环。
注意在$n$的最小因子$p$的意义下，只有$O(\sqrt p)$步。
我们考虑有两个变量，一个每次走一步，一个每次走两步，令$t$是。$\rho$尾巴的长度，$l$是环长，于是我们肯定可以在$O(t+l)$时间找到循环节。如果$2a - a$是环长$l$的倍数，并且都进入了环，那么必然重合。进入环前走了$t$步，进入环最多走了$l$步，于是是$O(t+l)$
总复杂度是$O(n^{\frac 1 4} polylog)$。我们平时用的$F(x) = x^2+c$，$c$随机，这种复杂度还没有证明。
筛素数
假设$p_m$是 mth 质数，$f(n,m)$表示$\leq n$的不含$p_1…p_m$作为因子的数，那么不难发现
$f(n,m) = f(n,m-1) - f(\lfloor\frac n {p_m} \rfloor ,m-1 )$
如果有$p_m^2 > n$那么$f(\lfloor \frac n {p_m} \rfloor ,m-1) = 1$
所以这个东西的复杂度是$O(n^{3/4})$可能还得除以 Log
想法类似 Min25
线性同余方程组
$m_i$互质，$M = \prod m_i , M_i = \frac M {m_i},M_i^{-1}$是$M_i$膜$m$逆元
$x \equiv \sum_{i=1}^{n} x_{i} M_{i} M_{i}^{-1} \pmod M$
不互质考虑增量法，每次把两个方程合并成一个大方程
$x \equiv a \pmod b,x\equiv c \pmod d$
那么$bt + a \equiv c\pmod d$
exgcd 解得$t \equiv t_0 \pmod {\frac{d}{(b,d)}}$
带回$x\equiv x_0 \pmod {[b,d]}$
一次合并复杂度$O(\log)$
阶
如果$(a,m) = 1$记$x$最小正整数使得$a^x\equiv 1 \pmod m$则称 $x$是$a$ 膜$m$的阶
原根
有原根的数$1,2,4,p^a,2p^a$
离散对数
若$g^x \equiv k \pmod p$则$\log_g k \equiv x \pmod p$
而且往往会让$g$为一个$\mod p$的原根
BSGS
设一个参数$l$，将$a^{0…l-1}$存到 hash table 里面。然后我们枚举$k \leq \frac {\varphi(m)-1} l$
每次查询 hash table 里面有没有$j$满许$a^{kl+j} \equiv b \pmod m$
复杂度$O(\sqrt {\varphi(m)})$
exBSGS
掉线
Lucas
$\binom n m \equiv \binom {n}{}$
- Min25 \sum f(i) = 1 + \sum_{p\in prime} \sum_{x最小只质因子为p}$