扩展中国剩余定理(EXCRT)
顾名思义就是把中国剩余定理给扩展了废话,听着感觉很(NB)但实际上不难理解(狗头)
(egin{cases}xequiv a_1 (mod m_1)\xequiv a_2(mod m_2)\……\xequiv a_k(mod m_k)end{cases})
当(m_1,m_2……m_k)两两不互质时
设前(k-1)个方程组成的同余方程组的一个解是(x)
且(M=prodlimits_{i=1}^{k-1}m_i)
则由中国剩余定理可得通解为(x+i*M(iin))
则加入第(k)个方程组后
我们其实就是要求(tin),使得
(x+t*Mequiv a_k(mod m_k))
将式子变形得
(t*Mequiv a_k-x(mod m_k))
其中(M,a_k,x)均为已知量
则式子可以看成(atequiv b(mod m_k))
可以用exgcd求解(t)
如果该同余式无解，则原方程组无解
否则前(k)个同余式构成的方程组的一个解即为(x_k=x+t*M)
(M)需随求解过程更新
简单地用人话来说就是
进行(k)次扩展欧几里得
例题
/*
@ author:pyyyyyy
-----思路------
下面的代码,ai和bi表示的比较混乱，建议自行百度一个看看
-----debug-------
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+2020;
int n,ai[N],bi[N];
int mul(int a,int b,int mod)
{
int ret=0;
while(b)
{
if(b&1) ret=(ret+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ret;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==0){
x=1;y=0;return a;
}
int g=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return g;
}
int excrt()
{
int x,y,k;
int M=ai[1],ans=bi[1];//构造出第一个同余方程的解
for(int i=2;i<=n;++i)
{
int a=M,b=ai[i],c=(bi[i]-ans%b+b)%b;//ax≡c(mod b)
int gcd=exgcd(a,b,x,y),lcm=b/gcd;//lcm是用来防止溢出的
if(c%gcd!=0) return -1;//无解的特判
x=mul(x,c/gcd,lcm);
ans+=x*M;
M*=lcm;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<=n;++i)
scanf("%lld %lld",&ai[i],&bi[i]);
cout<<excrt();
return 0;
}