527 中国剩余定理

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

void exgcd(LL a,LL b,LL &x,LL &y){
  if(b == 0){
    x = 1, y = 0; return;
  }
  LL x1, y1;
  exgcd(b, a%b, x1, y1);
  x = y1, y = x1-a/b*y1;
}
LL CRT(LL a[], LL b[], LL n){
  LL m = 1, ans = 0;
  for(int i=1;i<=n;i++)m*=a[i];
  for(int i=1; i<=n; i++){
    LL c = m/a[i], x, y;
    exgcd(c, a[i], x, y);
    ans = (ans+b[i]*c*x%m)%m;
  }
  return (ans%m+m)%m;
}
int main(){
  LL n, a[11], b[11];
  scanf("%lld", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%lld%lld", a+i, b+i);
  printf("%lld\n", CRT(a,b,n));
  return 0;
}