中国剩余定理
前置芝士
同余方程
问题
现给定一个方程组：(egin{cases}xequiv a_1(mod m_1)\xequiv a_2(mod m_2)\ cdots cdots\xequiv a_n(mod m_n)\end{cases})，需要求出(x)的值
分析
来举个简单的例子：
[egin{cases}xequiv 2(mod 3)\xequiv 3(mod 5)\xequiv 2(mod 7)\end{cases}
]
我们用递推的思想把一个大问题转化为小问题。先求出以下三个方程组的解。
[egin{cases}xequiv 1(mod 3)\xequiv 0(mod 5)\xequiv 0(mod 7)\end{cases}，egin{cases}xequiv 0(mod 3)\xequiv 1(mod 5)\xequiv 0(mod 7)\end{cases}，egin{cases}xequiv 0(mod 3)\xequiv 0(mod 5)\xequiv 1(mod 7)\end{cases}
]
举第一个方程的例子，可以转化为(35yequiv 1(mod 3))。
这时候，我们可以把方程组转化为同余方程来做。
而最先的那个方程组就可以用这些答案来表示。
我们用(egin{bmatrix}2\3\2 end{bmatrix})来表示(egin{cases}xequiv 2(mod 3)\xequiv 3(mod 5)\xequiv 2(mod 7)\end{cases})，则最后可以写成这样：
[egin{bmatrix}2\3\2 end{bmatrix}=2egin{bmatrix}1\0\0end{bmatrix}+3egin{bmatrix}0\1\0 end{bmatrix}+2egin{bmatrix}0\0\1 end{bmatrix}
]
这样，代码的实现就很显然了。
代码
#include <bits/stdc++.h>
#define ll long long
#define re register int
const int INF=1<<30;
const int mod=1e9+3;
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0;
ll f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
template <typename T>
inline void write(T x){
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9)
write(x/10);
putchar(x % 10 + '0');
return;
}
ll n,a[15],b[15],M=1,res;
inline ll exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {
x=1;y=0;
return a;
}
ll q=exgcd(b,a%b,y,x);
y-=a/b*x;
return q;
}
int main() {
read(n);
for(int i=1;i<=n;i++)
read(a[i]),read(b[i]);
for(re i=1;i<=n;i++)
M*=a[i];
for(re i=1;i<=n;i++) {
ll m,p,d,y;
m=M/a[i];
d=exgcd(m,a[i],p,y);
res=(res+m*p*b[i])%M;
}
if(res<0) res+=M;
write(res);
}