中国剩余定理

$\begin{cases} x\equiv a_1 (\mod p_1)\\ ....\\ x\equiv a_i (\mod p_i) \end{cases}$

$p_1,p_2…p_i$互质。

构造$x=\sum a_i\times m_i \times y$

因为

$m_iy\% p_j=0(j\neq i), m_i=sum/p_i\\ m_i y\equiv a_i(\mod p_i)\\$

扩展欧几里得即可。

扩展中国剩余定理

$\begin{cases} x\equiv a_1 (\mod p_1)\\ ....\\ x\equiv a_i (\mod p_i) \end{cases}$

$p_1,p_2…p_i$不互质。

$\begin{cases} x\equiv a_1 (\mod p_1)\\ x\equiv a_2 (\mod p_2) \end{cases} \rightarrow x\equiv b (\mod c)\\ k_1p_1+a_1=k_2p_2+a_2\\ k_1p_1-k_2p_2=a_2-a_1\\$

扩展欧几里得判断是否有解

$设gcd(p1,p2)=d,a2-a1=pd\\ K1=p\times (\frac{p1}{d})^{-1}(\mod \frac{p_2}{d}),可以解出来\\ 需要最非负数\rightarrow k1=K+y\times \frac{p_2}{d}\\ x=(K+y\times \frac{p_2}{d})p1+a1\\ b=Kp1+a1,c=lcm(p1,p2)$