caioj 1155 同余方程组(模版)

第一步，和同余方程一样，转化一下

两式相减得

这就转化为了求不定方程，用exgcd

求出x，要化成最小正整数解，避免溢出

然后可以求出P出来。

这个时候要把前两个式子转化成一个式子

设求出来的是P’

则有 

这个就转化成了新的m1和b1

然后就一直求下去即可

最终b1就是答案

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;void exgcd(ll a, ll b, ll& d, ll& x, ll& y)
{if(!b) { d = a; x = 1; y = 0; return; }else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}int main()
{ll n, b1, m1, b2, m2;scanf("%lld%lld%lld", &n, &b1, &m1);bool ok = true;REP(i, 1, n){scanf("%lld%lld", &b2, &m2);ll A, B, K, x, y, d;A = m1, B = m2, K = b2 - b1;exgcd(A, B, d, x, y);	if(K % d != 0) ok = false;x *= K / d; int mod = B / d;x = (x % mod + mod) % mod;b1 = m1 * x + b1; //这里顺序要注意m1 = m1 / d * m2;  } if(!ok) puts("no solution!");else printf("%lld\n", b1);return 0;
}