Chinese remainder theorem acwing 204. strange way of expressing integers

Chinese remainder theorem AcWing 204. Strange way to express integers

Original link

AcWing 204. Strange way to express integers

Algorithm tags

Math knowledge Congruence equation Expand the Chinese Remainder Theorem

Ideas

The picture is extracted from the solution of the question

Code

#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105;
int a[N][N], eps = 1e-8;
int n;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x=1, y=0;
        return a;
    }else{
        int d=exgcd(b, a%b, y, x);
        y-=a/b*x;
        return d; 
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n=read();
    int x=0, m1=read(), a1=read();
    rep(i, 0, n-1){
        int m2=read(), a2=read();
        int k1, k2;
        int d=exgcd(m1, m2, k1, k2);
        if((a2-a1)%d){
            x=-1;
            break;
        }
        k1*=(a2-a1)/d;
        k1=(k1 % (m2/d) + m2/d) % (m2/d);
        x=k1*m1+a1;
        int m=abs(m1/d*m2);
        a1=k1*m1+a1;
        m1=m;
    }
    if(x!=-1){
        x = (a1 % m1 + m1) % m1;
    }
    printf("%lld",x);
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support