题意：
给出n个模方程x=a(mod r) 求x的最小解
题解：
这就是个线性模方程组的模版题- - 但是有一些要注意的地方
extgcd算出来的解x可能负数 要让x=(x%mo+mo)%mo
而且mo不是等于lcm(r1,r2) 而是r2/gcd(r1,r2)
代码：
#include <cstdio>
typedef long long ll;
ll n,a,r;
ll extgcd(ll &x,ll &y,ll a,ll b){
if (!b){
x=,y=;
return a;
}else{
ll res=extgcd(x,y,b,a%b);
ll t=x;
x=y;
y=t-a/b*y;
return res;
}
}
int main(){
while (scanf("%I64d",&n)!=EOF){
scanf("%I64d%I64d",&r,&a);
ll x,y,a1,r1;
bool bo=;
for (ll i=;i<=n;i++){
scanf("%I64d%I64d",&r1,&a1);
ll gc=extgcd(x,y,r,r1);
if ((a1-a)%gc) bo=;
ll mo=r1/gc;
x=(x*(a1-a)/gc%mo+mo)%mo;
a+=r*x;
r*=r1/gc;
}
if (!bo) puts("-1");
else printf("%I64d\n",a);
}
}