题目
自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。
举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了；如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去；如果建造了 7 个猪圈，还有 2 头没有地方去。
你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？
输入格式
第一行包含一个整数 n，表示建立猪圈的次数；
接下来 n 行，每行两个整数 ai bi ，表示建立了 ai 个猪圈，有 bi 头猪没有去处。
你可以假定 ai, aj 互质。
输出格式
输出仅包含一个正整数，即为曹冲至少养猪的数目。
数据范围
1 < n <10
1 < b_i < a_i < 1100000
所有a_i的乘积不超过 10^18
输入样例：
3
3 1
5 1
7 2
输出样例：
16
题解
中国剩余定理裸题,
对于x mod m1 = a1 , x mod m2 = a2 … x mod mn = an,
一 . 设M = m1 * m2 * … mn; m[i] = M / mi , 设 m[i] * t[i] mod mi = 1;
二 : x += a[i] * m[i] * t[i]; ( 1<= i <= n);
m[i]已知,M已知,那么m[i] * ti mod mi = 1 用扩展欧几里求得满足得ti;, 然后累加即可
最后记得ans % M,这样才是最小的
对于这个题来说,mi * ti mod a[i] = 1,求得 ti .
int n;
ll a[MAXN],t[MAXN],b[MAXN];
ll M;ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x = 1,y = 0;return a;} ll d = exgcd(b,a%b,y,x);y -= a/b * x;return d;
}int main(){
scanf("%d",&n);M = 1;for(int i=1;i<=n;i++){
scanf("%lld %lld",&a[i],&b[i]);M *= a[i];}ll ans = 0;for(int i=1;i<=n;i++){
ll mi = M / a[i];ll ti,y;exgcd(mi,a[i],ti,y);ans += b[i]*mi*ti;}ans = (ans % M + M) % M; printf("%lld\n",ans);return 0;
}