Strange way of expressing integers (expanding Chinese remainder theorem)

Topic link

https://www.acwing.com/problem/content/description/206/

Ideas

For this question , We have to solve n An equation that satisfies the condition , We first consider the case of satisfying two equations ：
$X\equiv m_{1}mod{a}_1$
$X\equiv m_{2}mod{a}_2$
This equation can also be written in the following format , Assume an arbitrary integer $k_i$
$X\equiv k_i{a}_i+m_{i}mod{a}_i$
So we get ：
$k_1{a}_1+m_1=k_2{a}_2+m_2$
namely $k_1{a}_1-k_2{a}_2=m_2-m_1$

set up d by $gcd(a_1,a_2)$

If $d|m_2-m_1$ Then the equation has a solution , We can solve by extending Euclidean algorithm k1,k2 A solution of

set up p For any integer , And because the solution is not unique , So we can put k1 The general solution of is written in the form ：
$k1=k1+p\frac{a_2}{d}$
Empathy k2 The general solution of can be written as ：
$k2=k2+p\frac{a_1}{d}$
Then we will k1 The general solution formula can be substituted into the original equation ：
$X\equiv ((k_1+p\frac{a_2}{d})a_1+m1)mod{a}_1$
$X\equiv (P\frac{a_1\ast a_2}{d}+a_1{k}_1+m_1)mod{a}_1$
$X\equiv (P\times lgm(a_1,a_2)+(a_1{k}_1+m_1))mod{a}_1$
Then at this time, we were surprised to find that this is not the format of the formula we began to transform , So we found that we can merge the two equations through this operation , Then we will n The equations are merged into one equation , In the end $X\equiv P{X}_0+m_{1}mod{X}_0$ So direct output $m_1$ Just fine
Be careful ：
1. Because the data is very limited, we should ensure that k1 Is a minimum positive number solution
2. final $m_1$ It could be negative , It's best to take the mold first, then add the modulus, and then take the mold , Guarantee non negative

Code

#include<bits/stdc++.h>
using namespace std;
//---------------- Custom part ----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

ll ksm(ll a,ll b) {
    
	ll ans = 1;
	for(;b;b>>=1LL) {
    
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){
    return -x & x;}

const int N = 2e6+10;
//---------------- Custom part ----------------
int t,n,m,q,a[N];

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

void slove(){
    
	cin>>n;
	ll a1,m1;
	cin>>a1>>m1;
	bool fg = true;
	for(int i = 1;i < n; ++i) {
    
		ll a2,m2;
		cin>>a2>>m2;
		ll k1,k2;
		ll d = exgcd(a1,a2,k1,k2);
		if((m2 - m1) % d){
    
			fg = false;
			break;
		}
		k1 *= (m2-m1)/d;// Double 
		ll t = abs(a2 / d);
		k1 = (k1 % t + t) % t;// Become the smallest positive integer solution, otherwise it will overflow 
		
		m1 = a1 * k1 + m1;
		a1 = (a1 / d  * a2);
	}
	if(fg){
    
		cout<< (m1 % a1 + a1) % a1 <<endl;
	}
	else{
    
		cout<< "-1"<<endl;
	}
}

int main()
{
    
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	t = 1;
	while(t--){
    
		slove();
	}
	return 0;
}