中国剩余定理详解

\(\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>
using namespace std;
long long C=1;
int b[11],n,a[11];
struct p
{
  long long x,y;
} ;
p exgcd(long long a,long long b)//标准exgcd
{
  p M;
  if(b==0)
  {
    M.x=1,M.y=0;
    return M;
  }
  M=exgcd(b,a%b);
  p ANS;
  ANS.x=(M.y);
  ANS.y=(M.x-a/b*M.y);
  return ANS;
}
int main()
{
  cin>>n;
  for(int i=1; i<=n; i++)
  {
    cin>>a[i];
    C*=a[i];//即上文的S
    cin>>b[i];
  }
  long long ans=0;
  for(int i=1; i<=n; i++)
  {
    long long sum;
    sum=exgcd(C/a[i],a[i]).x;//求解Sizi+aiyi=gcd(Si,ai)
    sum*=(C/a[i]);//进而求出xi
    sum%=C;
    ans+=(sum*b[i])%C;//累加
    ans=(ans+C)%C;//防负数取模
  }
  cout<<ans;
  return 0;
}