题意

给定 2n 个整数$a_1,a_2....a_n$和$m_1,m_2,m_3…m_n$求一个最小的非负整数 x，满足∀i∈[1,n],$x\equiv m_i(mod\ a_i)$

输入格式

第1 行包含整数 n。

第 2. n+1行：每行包含两个整数ai和mi,数之间用空格隔开。

输出格式

输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在64位整数范围内。

数据范围

1≤ai≤$2^{31}-1$
0≤mi<ai
1≤n≤25

输入样例：

2
8 7
11 9

输出样例：

31

分析

由于是$m_i$并不两两互质，不能使用中国剩余定理。

但是假设前k-1个能找到答案$x_{k-1}$，mm前$m_1 \to m_{k-1}$的最小公倍数

则如果第k个有解

$x_k=x_{k-1}+lcm(mm,m_k)*p$

带入同余方程后可以得到

$x_{k-1}+lcm(mm,m_k)*p\equiv a_i(mod \ m_k)$

变换后得到
$q\*m_k+lcm(mm,m_k)*p=a_i-x_{k-1}$

接下来使用扩展欧几里得定理就可以解决了

代码

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

int const N=30;
ll n,m[N],a[N],mm,t,ty,x;

ll gcd(ll x,ll y){
    if(y==0) return x;
    else return gcd(y,x%y);
}

ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
}

bool check(ll a,ll b,ll c){
    ll d=gcd(a,b);
    if(c%d==0) return 1;
    return 0;
}

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll z=x; x=y; y=z-y*(a/b);
    return d;
}

ll get_pos_min(ll a,ll b){ return ((a%b)+b)%b;}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>m[i]>>a[i];
    x=get_pos_min(a[1],m[1]);mm=m[1];
    for(int i=2;i<=n;i++){
        if(!check(mm,m[i],a[i]-x)){
            cout<<-1<<endl;
            return 0;
        }                                
        exgcd(mm,m[i],t,ty);
        t*=(a[i]-x)/gcd(mm,m[i]);
        t=get_pos_min(t,m[i]/gcd(mm,m[i]));
        x+=t*mm;
        mm=lcm(mm,m[i]);
    }
    cout<<x<<endl;
    return 0;
}