扩展中国剩余定理

模板题：P4777

前置芝士：扩展欧几里得（exgcd）

不需要中国剩余定理

问题：求

\(\begin{cases}x\equiv m_1\ (\mod\ a_1)\\x\equiv m_2\ (\mod\ a_2)\\ ...\\x\equiv m_3\ (\mod\ a_3)\end{cases}\)

的最小整数解

我们可以先关注前两个方程

简单转换，可得

\(\begin{cases}x=k_1\times a_1+m_1\\x=k_2\times a_2+m_2\end{cases}\)

所以

\(k_1 \times a_1+m_1 = k_2\times a_2+m_2\)
\(k_1\times a_1-k_2\times a_2 = m_2-m_1\)

标准的拓欧板子，我们先用拓欧求出\(k_1\)的一个特解\(kk_1\)

接着发现\(k_1\)的通解为\(kk_1+k\times \frac{a_2}{\gcd(a_1,a_2)}\)

带入\(x=k_1 \times a_1+m_1\)

得

\(x=(kk_1+k\times \frac{a_2}{\gcd(a_1,a_2)})\times a_1+m_1\)
\(\ \;\,\,=a_1\times kk_1+m_1+k \times \operatorname{lcm}(a_1,a_2)\)

现在很明显了，让 \(a_1\times kk_1+m_1\) 作新的\(m\) , \(\operatorname{lcm}(a_1,a_2)\) 作新的\(a\)

将这个柿子和接下来的柿子滚雪球一样一直合并，最后得出的最终方程中的\(m\)即为答案，记得化成最小正整数

注意点：

\(1.\) 若合并过程中出现无解，即在求解特解\(kk1\)时出现\(\gcd(a_1,a_2) \nmid (m_2-m_1)\)整个方程就都无解，直接退出（当然这里保证有解）

\(2.\) 有一个大数据要__int128或龟速乘，快速乘之类的，请注意

代码被我吃了