数论全家桶

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
$$

用于求解同于方程组
$$
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相加

相比于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