中国剩余定理 & ex

中国剩余定理

引入

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。

具体解法分下面三步：

① 找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。

② 用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗215∗2+21∗3+70∗2得到和233。

③ 用233除以3、5、7的最小公倍数105，得到余数23，这个余数23就是符合条件的最小数。

分析

分析过程中涉及到的同余公式有

① 若a%b=c,则有(a+kb)%b=c (k为非零整数)。② 若a%b=c,则有(a*k)%b=kc (0<k<b)。

令n1%3=2，n2%5=3，n3%7=2

通过公式①可以得到：

为使n1+n2+n3的和满足除以3余2，n2和n3必须是3的倍数。

为使n1+n2+n3的和满足除以5余3，n1和n3必须是5的倍数。

为使n1+n2+n3的和满足除以7余2，n1和n2必须是7的倍数。

因此，为使n1+n2+n3的和作为“孙子问题”的一个最终解，需满足：

n1除以3余2，且是5和7的公倍数。

n2除以5余3，且是3和7的公倍数。

n3除以7余2，且是3和5的公倍数。

所以，孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1，从3和7的公倍数中找一个除以5余3的数n2，从3和5的公倍数中找一个除以7余2的数n3，再将三个数相加得到解。

在求n1，n2，n3时又用了一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。

最后，我们还要清楚一点，n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉3，5，7的公倍数105即可。所以（n1+n2+n3）%105就是最终的最小解。

实现

我们可以利用这种思想，将其化为更一般的情况。(模数m两两互质)

$\left\{\begin{matrix} x\equiv a_{1} \ \ (mod \ m_{1}) \\x\equiv a_{2} \ \ (mod \ m_{2}) \\............... \\x\equiv a_{n} \ \ (mod \ m_{n}) \end{matrix}\right.$

令 $M=\prod_{i=1}^{n}m_{i}\ ,\ M_{i}=\frac{M}{m_{i}}$ ， $t_{i}$ 为 $M_{i}$ 在模 $m_{i}$ 下的逆元，有 $M_{i}t_{i}\equiv 1\ (mod \ m_{i})$ 。

那么 $x=a_{1}M_{1}t_{1}+a_{2}M_{2}t_{2}+...+a_{n}M_{n}t_{n}+kM$

$=\sum_{i=1}^{n}a_{i}M_{i}t_{i} \ \ (mod \ M)$

P3868 [TJOI2009]猜数字

#include<bits/stdc++.h>
using namespace std;
int k;
long long a[15],b[15],M=1;
long long CRT();
void exgcd(long long a,long long b,long long &x,long long &y);
long long quick_add(long long a,long long b);
int main()
{
  int i;
  scanf("%d",&k);
  for(i=1;i<=k;i++) scanf("%lld",&a[i]);
  for(i=1;i<=k;i++) scanf("%lld",&b[i]),M*=b[i];
  for(i=1;i<=k;i++) a[i]=(a[i]%b[i]+b[i])%b[i];
  printf("%lld",CRT());
  system("pause");
  return 0;
}
void exgcd(long long a,long long b,long long &x,long long &y)
{
  if(b==0)
  {x=1;y=0;return ;}
  exgcd(b,a%b,x,y);
  long long t=x;
  x=y;
  y=t-a/b*y;
}
long long quick_add(long long a,long long b)
{
  long long ans=0;
  while(b)
  {
    if(b&1) ans=(ans+a)%M;
    b>>=1;
    a=(a+a)%M;
  }
  return ans;
}
long long CRT()
{
  long long m,x,y,ans=0;
  for(int i=1;i<=k;i++)
  {
   m=M/b[i];
   exgcd(m,b[i],x,y);
   x=(x%b[i]+b[i])%b[i];
   ans=(ans+quick_add(quick_add(m,x),a[i]))%M;
  }
  return ans;
}

View Code

扩展中国剩余定理

扩展中国剩余定理可以求当m并不严格满足两两互素的同余方程组的解。

扩展中国剩余定理和中国剩余定理没什么卵关系：）。

$\left\{\begin{matrix} x\equiv a_{1} \ \ (mod \ m_{1}) \\x\equiv a_{2} \ \ (mod \ m_{2}) \\............... \\x\equiv a_{n} \ \ (mod \ m_{n}) \end{matrix}\right.$

先从同余方程组中随意找出两个方程(比如前两个) $x\equiv a_{1} \ \ (mod \ m_{1})\ \ ,\ \ x\equiv a_{2} \ \ (mod \ m_{2})$

转换为

$x\equiv a_{1} \ \ (mod \ m_{1})\rightarrow x=a_{1}+k_{1}m_{1}$

$x\equiv a_{2} \ \ (mod \ m_{2})\rightarrow x=a_{2}+k_{2}m_{2}$

合并

$k_{1}m_{1}+k_{2}m_{2}=a_{2}-a_{1}$

令d=gcd(m1,m2)，通过扩欧得到k'为 $k_{1}m_{1}+k_{2}m_{2}=d$ 的特解，则 $k_{1}$ 的解集为 $k'\frac{a_{2}-a_{1}}{d}+\frac{m_{2}}{d}t\ , t\in \mathbb{Z}$ (若(a2-a1)%d!=0，则无解)

将解集带回 $x=a_{1}+k_{1}m_{1}$ ，得到

$x=a_{1}+k'\frac{(a_{2}-a_{1})*m_{1}}{d}+\frac{m_{2}*m_{1}}{g}*t$

转换

$x\equiv a_{1}+k'\frac{(a_{2}-a_{1})*m_{1}}{d} \ \ (mod\ \frac{m_{2}*m_{1}}{g})$

可以看到，通过以上的方式，将两个同余式等价为了一个同余式。所以当我们有n个同余式时，我们可以通过(n-1)次上述操作将n个同余式变为一个同余式，从而求解。

P4777 【模板】扩展中国剩余定理（EXCRT）

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long qucik_add(long long a,long long b,long long p);
long long exgcd(long long a,long long b,long long &x,long long &y);
long long excrt(int n);
long long a[maxn],m[maxn];
int main()
{
  int n,i;
  scanf("%d",&n);
  for(i=1;i<=n;i++) scanf("%lld%lld",&m[i],&a[i]);
  printf("%lld
",excrt(n));
  system("pause");
  return 0;
}
long long qucik_add(long long a,long long b,long long p)
{
  long long ans=0;
  int f=1;
  if(a<0) a=-a,f*=-1;
  if(b<0) b=-b,f*=-1;
  while(b)
  {
    if(b&1) ans=(ans+a)%p;
    b>>=1;
    a=(a+a)%p;
  }
  return ans*f;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
  if(!b)
   {x=1;y=0;return a;}
  long long d=exgcd(b,a%b,x,y);
  long long t=x;
  x=y;
  y=t-a/b*y;
  return d;
}
long long excrt(int n)
{
  long long A=a[1],M=m[1],d,x,y;
  for(int i=2;i<=n;i++)
  {
   d=exgcd(M,m[i],x,y);
   if((A-a[i])%d!=0) return -1;
   x=(qucik_add(x,(a[i]-A)/d,m[i]/d)+(m[i]/d))%(m[i]/d);
   A+=x*M;
   M*=m[i]/d;
  }
  return A;
}

View Code