#define first f #define second s #define ll long long #define mp make_pair #define pb push_back #include<bits/stdc++.h> #define pii pair<ll,ll> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=2e5+5; ll a[maxn],r[maxn]; ll ex_gcd(ll a1,ll b1,ll &x,ll &y) { if(b1==0){ x=1;y=0;return a1; } ll r=ex_gcd(b1,a1%b1,x,y); ll t=x;x=y; y=t-a1/b1*y; return r; } ll CRT(int n) { ll A=a[1],R=r[1],x,y,temp,d; for(int i=2;i<=n;i++){ d=ex_gcd(A,a[i],x,y); if((R-r[i])%d){return -1;} temp=a[i]/d; x=x*((R-r[i])/d); x=(x%temp+temp)%temp; R-=A*x; A*=temp; R=(R%A+A%A); } return R==0?A:(R%A+A)%A; } int main() { int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%lld%lld",&a[i],&r[i]); } printf("%lld\n",CRT(n)); } return 0; }
全部评论
(2) 回帖