CRT&&ExCRT

CRT和ExCRT是用来求解如下的线性同余方程组的：

[xequiv a_1 (mod p_1)\ xequiv a_2 (mod p_2)\ ……\ xequiv a_n (mod p_n)\ ]

先考虑特殊一点的情况：任意的pi互质。可以用CRT解决。

CRT的核心思想就是构造。

考虑构造出每一个同余方程的解，并且使它们可以直接合并成最终答案，即两两之间互不影响。

[令：\ PP=sum_{i=1}^n{p_i}\ Pi=PP/pi\ Ti为方程：Ti*Piequiv 1 (mod p_i) 的解\ 那么最后ans=sum_{i=1}^n a_i*T_i*P_i ]

正确性很显然，回代进每一个方程即可。

但是这个的正确性是基于pi互质的，如果不互质显然这个就不一定成立了。

那么怎么办呢？

不妨顺次考虑每一个方程，假设现在考虑到了第i个方程，前面i-1个方程的的解已经求出记为S。

[令: PP=lcm(p_1,p_2,…,p_{i-1})\ 则前i个方程的通解：X=S+k*PP (Kin Z) ]

假设第i个方程存在一个根(X_0)，满足(X_0=S+T*PP)，那么(X_0)为前i个方程的解。

所以现在的问题转化为求一个T，使之满足：

[S+T*PPequiv a_i (mod p_i) ]

来一波转化：

[S+T*PPequiv a_i (mod p_i)\ iff T*PPequiv a_i-S (mod p_i)\ iff T*frac{PP}{gcd(PP,p_i)}equiv frac{a_i-S}{gcd(PP,p_i)} (mod frac{p_i}{gcd(PP,p_i)}) ]

此时上方程可以用Exgcd解决。

所以整个问题得到解决！

signed main()
{
	RG int i,x,y,d,fl,ans,now,res,gcd;
	scanf("%lld
",&n);
	for (i=1;i<=n;++i) scanf("%lld %lld",&m[i],&a[i]);
	fl=0,ans=a[1],now=m[1]
    for (i=2;i<=n;++i) {
		gcd=exgcd(now,m[i],x,y),res=(a[i]-ans%m[i]+m[i])%m[i];
		if (res%gcd!=0) {fl=1;break;} //不能继续整除说明无解
		else d=m[i]/gcd,x=mul(x,res/gcd,d),ans+=x*now,now*=d,ans=(ans%now+now)%now;  	
	}
	printf("%lld
",fl?-1:ans);	
	return 0;
}   //ExCRT