\(\texttt{例题}\)
韩信点兵， \(a_1a_1\) 个点，还剩 \(b_1\) 个兵；\(a_2a_2\) 个点，还剩 \(b_2\) 个兵……\(a_na_n\) 个点，还剩 \(b_n\) 个兵。
请问韩信手下有几个兵？
其中，对于任意的 \(a_i\) 与 \(a_j(i≠j,1\le i,j\le n)\) 之间两两互质。
\(\texttt{思路}\)
将题目形式化表述出来，即求满足：
\(\begin{cases}x\equiv b_1(mod\quad a_1)\\x\equiv b_2(mod\quad a_2)\\.........\\x\equiv b_n(mod\quad a_n)\end{cases}\)
的 \(x\) 的值。
根据余数的可加性，我们可以将题目传换成，求满足：
\(\begin{cases}x_1\equiv b_1(mod\quad a_1)\\x_1\equiv 0(mod\quad a_2)\\.........\\x_1\equiv 0(mod\quad a_n)\end{cases}\quad \begin{cases}x_2\equiv 0(mod\quad a_1)\\x_2\equiv b_2(mod\quad a_2)\\.........\\x_2\equiv 0(mod\quad a_n)\end{cases}...\begin{cases}x_n\equiv 0(mod\quad a_1)\\x_n\equiv 0(mod\quad a_2)\\.........\\x_n\equiv b_n(mod\quad a_n)\end{cases}\)
的 \(x_1,x_2,...,x_n\) 的和。
我们再将同余方程右边的 \(b\) 全部换成 \(1\)，则题目变成，求满足：
\(\begin{cases}x_1\equiv 1(mod\quad a_1)\\x_1\equiv 0(mod\quad a_2)\\.........\\x_1\equiv 0(mod\quad a_n)\end{cases}\quad \begin{cases}x_2\equiv 0(mod\quad a_1)\\x_2\equiv 1(mod\quad a_2)\\.........\\x_2\equiv 0(mod\quad a_n)\end{cases}...\begin{cases}x_n\equiv 0(mod\quad a_1)\\x_n\equiv 0(mod\quad a_2)\\.........\\x_n\equiv 1(mod\quad a_n)\end{cases}\)
的 \(x_1b_1+x_2b_2+...+x_nb_n\) 。
我们将每一个同余方程组单独拿出来看，比如说第 \(i\) 个：
\(\begin{cases}x_i\equiv 0(mod\quad a_1)\\.........\\x_i\equiv 1(mod\quad a_i)\\.........\\x_i\equiv 0(mod\quad a_n)\end{cases}\)
因为 \(x_i\) 要是 \(a_1,a_2,...,a_{i-1},a_{i+1},...,a_n\) 的倍数，所以我们可以设 \(z_1=x_1/(a_1a_2...a_{i-1}a_{i+1}...a_n)\)，
接着，这个同余方程组可以转化为一个同余方程，即：
\(a_1\times a_2\times ...\times a_{i-1}\times a_{i+1}...\times a_n\times z_1\equiv1(mod\quad a_1)\)
设 \(a_1\times a_2\times ...\times a_{i-1}\times a_{i+1}...\times a_n=S\)，然后将其转换为普通的等式：
\(Sz_i+a_iy_i=1\)
由于题目中有规定：
ai与aj之间相互互质
所以 \(gcd(S,a_i)=1\)；
那么原式又变成了：
\(Sz_i+a_iy_i=gcd(S,a_i)\)
我们只需要执行 \(n\) 次扩展欧几里得，分别求出 \(z_1,z_2,...,z_n\)，然后再求出 \(x_1,x_2,...,x_n\) ，
接着计算 \(x_1b_1+x_2b_2+...+x_nb_n\) 就好了。
\(\texttt{代码}\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=15;
inline ll read(){
register ll x=0;
register char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x;
}
ll n,mod;
ll a[maxn],b[maxn];
void getmod(ll &x)//取模
{
x=(x%mod+mod)%mod;
}
void exgcd(ll a,ll b,ll &x,ll &y,ll &gcd)
//扩展欧几里得求逆元
{
if(!b)
{
x=1,y=0,gcd=a;
return ;
}
exgcd(b,a%b,x,y,gcd);
register int tmp=y;
y=x-(a/b)*y,x=tmp;
}
int main()
{
n=read(),mod=1;
for(register int i=1;i<=n;i++)
a[i]=read(),b[i]=read(),mod*=a[i];
register ll ans=0,x,y,gcd;
for(register int i=1;i<=n;i++)
{
exgcd(mod/a[i],a[i],x,y,gcd);//求出zi
ans+=(x*b[i]*(mod/a[i]))%mod,getmod(ans);//求出xi并累加答案
}
printf("%lld\n",ans);
return 0;
}