Warning: session_start(): open(/tmp/sess_e826e51cc485c99bac78fb8ac51e6fb2, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 扩展中国剩余定理 ======
===== 例题 =====
[[https://www.luogu.com.cn/problem/P4777|【模板】扩展中国剩余定理]]
**题意**：求解以下同余方程组
$$
\left\{\begin{array}{ccc}
x &\equiv&a_1\pmod{m_1}\\
x &\equiv&a_2\pmod{m_2}\\
&\vdots&\\
x &\equiv& a_n\pmod{m_n}\\
\end{array}\right.
$$
不保证 $m_i$ 互质，保证有解
**题解**：
对于只有 $2$ 个方程的情况：$x\equiv a_1\pmod{m_1};x\equiv a_2\pmod{m_2}$，等价于 $x=a_1+m_1t_1=a_2+m_2t_2$，即 $m_1t_1-m_2t_2=a_2-a_1$，用扩展欧几里得解出 $t_1$，（若无解则方程组无解），从而得到 $x$ 的解 $x\equiv x_0\pmod{\text{lcm}(m_1,m_2)}$，从而将两个方程合并为一个。$n$ 个方程即执行 $n-1$ 次扩展欧几里得算法，不断合并方程，直至得到最终解。注意过程中乘法要用快速乘避免溢出，注意取模时的模数是什么。
**代码**：
#include
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll m[N],a[N];
ll gcd(ll x,ll y){
return !y?x:gcd(y,x%y);
}
ll lcm(ll x,ll y){
return y/gcd(x,y)*x;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;return;
}
exgcd(b,a%b,y,x);
y-=x*(a/b);
}
ll mul(ll x,ll y,ll mod){
ll ans=0;
x%=mod;y%=mod;
while(y){
if(y&1) ans=(ans+x)%mod;
x=(x+x)%mod;
y>>=1;
}
return ans;
}
ll calc(ll M,ll mi,ll c,ll x0){
ll g=gcd(M,mi);
ll x,y;
exgcd(M,mi,x,y);
ll temp=lcm(M,mi);
c=(c%mi+mi)%mi;
ll ret=mul(x,c/g,mi);
ret=(ret%mi+mi)%mi;
return (mul(ret,M,temp)+x0%temp)%temp;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld %lld",&m[i],&a[i]);
ll M=m[1];
ll ans=a[1]%M;
for(int i=2;i<=n;i++){
ans=calc(M,m[i],a[i]-ans,ans);
M=lcm(M,m[i]);
ans=(ans+M)%M;
}
printf("%lld",ans);
return 0;
}