孙子定理

链接：https://www.nowcoder.com/acm/contest/75/B
来源：牛客网

题目描述

uu遇到了一个小问题，可是他不想答。你能替他解决这个问题吗？
问题：给你k对a和r是否存在一个正整数x使每队a和r都满足：x mod a=r，求最小正解x或无解。

输入描述:

第一行是正整数k(k<=100000)
接下来k行，每行有俩个正整数a，r(100000>a>r>=0)

输出描述:

在每个测试用例输出非负整数m，占一行。
如果有多个可能的值，输出最小的值。
如果没有可能的值，则输出-1。

示例1

输入

2
8 7
11 9

输出

31

#include<bits/stdc++.h>
using namespace std;
 
long long a[100006],m[100006];
 
void ex(long long b,long long c,long long &d,long long int &x,long long int &y)
{
    if(!c){
        d=b; x=1; y=0;
    }
    else{
        ex(c,b%c,d,y,x);
        y-=x*(b/c);
    }
}
 
long long china(int n)
{
    long long m1,r1;
    m1=a[0],r1=m[0];
    for(int i=1;i<n;i++){
        long long m2=a[i],r2=m[i];
        long long int x,y,d,e;
        ex(m1,m2,d,x,y);
        e=r2-r1;
        if(e%d){
            return -1;
        }
        long long t=m2/d;
        x=(e/d*x%t+t)%t;
        r1=m1*x+r1;
        m1=m1*m2/d;
    }
    if(n==1&&r1==0) return m1;
    return r1;
}
 
int main()
{
    long long n;
    while( ~scanf("%lld",&n)){
        for(int i=0;i<n;i++)
            scanf("%lld%lld",&a[i],&m[i]);
 
        long long out;
        out = china(n);
 
        printf("%lld
",out);
        memset( a, 0, sizeof(a));
        memset( m, 0, sizeof(m));
    }
 
    return 0;
}

　　运用扩展欧几里得算法求出乘法逆元，逆元乘上除数相加。