数论全家桶
目录欧拉定理
1.结论
$$
∀a,m∈Z且gcd(a,m)=1，a^{\varphi(m)}\equiv1\ (mod\ m)
$$
欧拉定理的一个常见用法是对指数降幂。
应用当mod数质数时，有
$$
a^b \equiv a^{bmod\phi(m)} (mod m), gcd(a,m)=1;
$$
例如：https://www.luogu.com.cn/problem/P2480的化简
2.欧拉函数(小于他的并且与他互质的正整数数量和)
$$
φ(m)=∑(i=1，m−1) gcd(i,m)=1
$$
中国剩余定理CRT
用于求解同于方程组
$$
x\equiv ai(mod\ mi)
$$
为两两互质的整数，求x的解。
不管了，直接上求解方法
1.求出所有mod数的乘积，记为M，利用M/mi得到每个的Mi
2.找到Mi在modm下的逆元ti，就是求解
$$
Miti\equiv1(mod m)
$$
3.最后的解x就是所有的a_i* ti *Mi相加
EXCRT
相比于crt 而言，就是mi不互质了
前提：x的系数必须为1
问题同CRT，但是模数是任意的，并不要求互质。
这时，我们就不能保证存在逆元了。那么如何解决该问题呢？
考虑如何合并两个方程。如果我们找到了合并的方法，就能如法炮制将(n)个方程依次合并起来，得到答案。
$$
\left{
\begin{aligned}
x &\equiv a_1 \pmod{m_1} \
x &\equiv a_2 \pmod{m_2}
\end{aligned}
\right.
$$
去掉同余，化为不定方程
$$
\left{
\begin{aligned}
x &= m_1 y_1 + a_1 \
x &= m_2 y_2 + a_2
\end{aligned}
\right.
$$
于是得到
$$
m_1 y_1 + a_1 = m_2 y_2 + a_2
$$
只要找到一组满足该式的(y_1)和(y_2)，就能反算出(x)，实现合并。
而我们得到的是一个二元一次的不定方程，可以用exgcd求解。
化为标准式
$$
m_1 y_1 - m_2 y_2 = a_2 - a_1
$$
解就是了。如果没有解，说明同余方程组无解。
于是最后化得的合并式为
$$
x \equiv m_1 y_1 + a_1 \pmod{lcm(m_1,m_2)}
$$
至于思考的时候，我认为参考一下以下思考过程
在此之前，不妨先想想普通的扩展中国剩余定理是怎么做的，即所有 b_i=1b**i=1 的情况。
-
假设已经得到了前 i-1 组同余方程的解，记为 ans；
-
设 $M=\operatorname{lcm}(p_1,p_2,\ldots,p_{i-1})$，则对于任意的整数 x，ans+Mx 是前 i-1 组同余方程的通解；
-
我们想得到前 $i$ 组同余方程的解，就是想找到一个 x，满足 $ans+Mx\equiv a_i\pmod {p_i}；$
-
移项得 $Mx\equiv a_i-ans\pmod{p_i}；$
-
这类式子一看就是老扩欧了，转化成 Ax+By=C的形式用扩展欧几里得求解，即：
$(M)x+(p_i)y=(a_i-ans)$
详情可以参考：https://www.luogu.com.cn/blog/emptyset/solution-p4774
LUCAS定理
当mod数p是一个很小（30000没问题）的质数时，存在
$$
C_n^m\ mod \ p=C_{n/p}^{m/p}*C_{n\ mod \ p}^{m\ mod\ p}
$$
由此可以用于化简
卡特兰数
1.递推式（如下）：
$$
h(n)=h(n-1)(4n-2)/(n+1)，h(0)=1
$$
2.直接的计算（如下）：
$$
h_n=C_{2n}{n}-C_{2n}=C_{2n}^n/{(n+1)}
$$
3.常见应用
a.突多边形的划分方案
b.$ n$个点构成二叉树的种类数
c.按从小到大的顺序放到任意一个数x，都满足放在偶数位上的数字个数小于等于放在奇数位上的数字个数。
d.在网格图上，从$(0,0) $走到$(n,n) $并且不越过$y=x $这条直线的方案数
其实大多数都可以抽象为d来做
4.例题：https://www.luogu.com.cn/problem/P3200
经过推导后，要求上面的c条件，至于证明，可以看成放在偶数位置就是网格图上向上走1步，奇数位置就是向右走一步，最终要满足这个路径不越过$y=x$。
5.取$mod$问题：
如上题，$mod$数不一定为质数，而且n的范围很大（不能杨辉三角递推），那么该怎么办呢
分解这个$mod$数，然后用$crt$求解
考虑“直接计算”中的第二个等式,
标签：数论,定理,全家,pmod,ans,mod,互质,equiv From： https://www.cnblogs.com/linghusama/p/17616344.html