本来想自己写的，但是这个入写的太好了直接转载了
Tyih

扩展中国剩余定理（EXCRT）

​
题目：​P4777 - 洛谷​

简述

如果给定 个同余方程组

保证 是正整数， 是非负整数

现在要求找一个非负整数 ，使得 最小且满足这 同余方程

数据保证 不超过

做法

可以考虑将同余方程合并

对于一个合并完后的方程以及一个需要合并的方程：

可以推出：

即：

整理得：

我们就可以用 exgcd 求出 其中一个解。再同时乘 ，可以得到一个解 。

我们可以从其得到其通解为：

由前面我们可知 ，将 的通解带入，可以得到：

我们可以得到一个同余方程：

对于多个方程只需将其两两合并即可。
以上就是所有思路过程了。

Code

#include<bits/stdc++.h>
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define mod 998244353
#define ll __int128
#define lll long long
#define db double
#define pb push_back
#define MS(x,y) memset(x,y,sizeof x)
using namespace std;
const int N=1e5+5,M=1e5+5;
const ll INF=1ll<<60;
int n;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    else{
        ll aa=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return aa;
    }
}
ll A,B,x,y;
int main(){
    lll a,b;
    IOS;cin>>n;
    A=1;B=0;//因为 x mod 1 一定等于零
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        ll gd=exgcd(A,a,x,y);
        x=(B-b)/gd*x;
        B=B-A*x;
        A=a/gd*A;
        B=(B%A+A)%A;
    }
    lll ans=(B%A+A)%A;
    cout<<ans<<"\n";
    return 0;
}

相位移动至luogu
此题要开__int128

/**
 *　　┏┓　　　┏┓+ +
 *　┏┛┻━━━┛┻┓ + +
 *　┃　　　　　　　┃
 *　┃　　　━　　　┃ ++ + + +
 *  ████━████+
 *  ◥██◤　◥██◤ +
 *　┃　　　┻　　　┃
 *　┃　　　　　　　┃ + +
 *　┗━┓　　　┏━┛
 *　　　┃　　　┃ + + + +Code is far away from
 *　　　┃　　　┃ + bug with the animal protecting
 *　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug
 *　　　┃ 　　　　　　 ┣┓
 *　　  ┃ 　　　　　 　┏┛
 *　    ┗┓┓┏━┳┓┏┛ + + + +
 *　　　　┃┫┫　┃┫┫
 *　　　　┗┻┛　┗┻┛+ + + +
 */
#include <bits/stdc++.h>
using namespace std;
#define int __int128_t
#define lson now * 2, l, (l + r) / 2
#define rson now * 2 + 1, (l + r) / 2 + 1, r
#define pi pair<int, int>
int n, m;
template <typename T> inline void read(T &x) {
  x = 0;
  register char c = getchar();
  register short f = 1;
  while (c < '0' || c > '9') {
    if (c == '-')
      f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  x *= f;
}
template <typename T, typename... Args> inline void read(T &x, Args &...temps) {
  read(x), read(temps...);
}
void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10;
    x /= 10;
  } while (x);
  while (top)
    putchar(sta[--top] + '0');
}
int a, b;
int A, B, x, y;
int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  } else {
    int aa = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return aa;
  }
}
void solve() {
  read(n);
  A = 1;
  B = 0;
  for (int i = 1; i <= n; i++) {
    read(a, b);
    int gd = exgcd(A, a, x, y);
    x = (B - b) / gd * x;
    B -= A * x;
    A = a / gd * A;
    B = (B % A + A) % A;
  }
  int ans = (B % A + A) % A;
  write(ans);
}
signed main() {
  int T = 1;
  // read(T);
  while (T--) {
    solve();
  }
  return 0;
}