RT.

这是我的代码：（ AC 100pts）

#define int __int_128
int exgcd(int a, int b, int &x, int &y)
{
	if(!b) 
	{
		x=1,y=0;
		return a;
	}
	int res=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return res;
}
......
struct Node{int a,mod;}; // 存储方程
il Node merge(Node a, Node b) // 请注意这个函数！
{
	int x,y;
	int tmp=exgcd(a.mod,-b.mod,x,y);
	if((b.a-a.a)%tmp) throw "OMG, No solution!";
	int p3=(b.a-a.a)/tmp;
	x*=p3,y*=p3;
	int new_mod=lcm(a.mod,b.mod);
	assert(a.mod*x-b.mod*y==b.a-a.a);
	return (Node){(((x*a.mod+a.a)%new_mod)+new_mod)%new_mod,new_mod};
}
il ll exCRT(vector<Node> dat)
{
	Node tmp=*dat.begin();
	for(vector<Node> :: iterator it=dat.begin()+1; it!=dat.end(); ++it)
	{
		// cerr<<(ll)tmp.a<<endl;
		tmp=merge(tmp,*it);
	}
	return (ll)tmp.a;
}
......

但是如果我们将 merge 函数换成如下写法，会发现连样例都过不去：

il Node merge(Node a, Node b)
{
	ll __x,__y;
	int tmp=exgcd(a.mod,b.mod,__x,__y);
	if((b.a-a.a)%tmp) throw "OMG, No solution!";
	int p1=a.mod/tmp,p2=-b.mod/tmp,p3=(b.a-a.a)/tmp;
	exgcd(p1,p2,__x,__y); // 注意这里
	int x=__x,y=__y;
	x*=p3,y*=p3;
	int new_mod=lcm(a.mod,b.mod);
    assert(a.mod*x-b.mod*y==b.a-a.a); // 这里会 assertion failed !
	return (Node){(((x*a.mod+a.a)%new_mod)+new_mod)%new_mod,new_mod};
}

但是为什么会造成这种错误呢？

这是我的推导：