中国剩余定理详解

中国剩余定理与扩展中国剩余定理

首先来看这个方程

$$\begin{cases} x≡a_{1}(mod\ b_1)\\ x≡a_{2}(mod\ b_2)\\ x≡a_{3}(mod\ b_3)\\ \cdots\\ x≡a_{n}(mod\ b_n) \end{cases}$$

求出上述x的最小正整数解，即为中国剩余定理。
有两种情况，第一种为$b_1$,$b_2$,$b_3$之间两两互质。
第二种情况为不互质时，也就是扩展中国剩余定理

中国剩余定理

设$M=b_1*b_2*\cdots*b_n$
因为$b_i$之间两两互质，所以M即为他们的最小公倍数。
再设$M_i=\frac{M}{b_i}$这里的$M_i$与上面的M没有关系。
此时我们得到

$$M^{-1}_iM_i≡1(mod\ b_i)$$

这里，$M^{-1}_i$,我们可以用扩展欧几里得求出，也就是$M_i$的数论逆元
左右两边同时乘上$a_i$,得到

$$a_i*M^{-1}_i*M_i≡a_i(mod\ b_i)$$

参考原方程$x≡a_i(mod\ b_i)$
得到$x=a_i*M_i*M^{-1}_{i}$
然后得到通解$x=\sum_{i=1}^n{a_i*M_i*M^{-1}_i}$

题目链接

模板

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fin(a,n) for(int i=a;i<=n;i++)
const int maxn=20;
ll a1[20],b1[20];
ll mul(ll a,ll b,ll mod)//求（a*b）%mod ，防止a*b炸ll 
{
 ll ans=0;
 while(b>0)
 {
 if(b&1)ans=(ans+a)%mod;//如果b对答案有贡献 
 a=(a+a)%mod;
 b>>=1;
}
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得 
{
 if(b==0)
 {
  x=1;
  y=0;
  return a;
 }
 ll ans=exgcd(b,a%b,x,y);
 ll temp=x;
 x=y;
 y=temp-(a/b)*y;
 return ans;
}
ll china(int n)//中国剩余定理 
{
 ll M=1,ans=0,x,y;
 fin(1,n)M*=b1[i]; 
 fin(1,n)
 {
  ll a,b;
  a=M/b1[i];//此处的按照ax+by=1的形式，因为互素所以等号右边恒为1.
  b=b1[i];
  exgcd(a,b,x,y);
  x=(x%b+b)%b;//求出最小的x 
     ans=(ans+mul(mul(a,x,M),a1[i],M))%M;//此处对应求和即ai*xi*mi 
 }
 return (ans+M)%M;
}
int main()
{
 int n;
 scanf("%d",&n);
 fin(1,n)scanf("%lld",&a1[i]);
 fin(1,n)scanf("%lld",&b1[i]);
 fin(1,n)a1[i]=(a1[i]%b1[i]+b1[i])%b1[i];//预处理数据 
 ll tans=china(n);
 printf("%lld",tans);
}

扩展中国剩余定理

扩展中国剩余定理就是上述的$b_i$不互质的时候。
我们看原方程

$$\begin{cases} x≡a_{1}(mod\ b_1)\\ x≡a_{2}(mod\ b_2)\\ x≡a_{3}(mod\ b_3)\\ \cdots\\ x≡a_{n}(mod\ b_n) \end{cases}$$

设第n个方程的解为x,$M=\prod_{i=1}^n$
那么前k个方程的通解为x+k*m.
把通解带入k+1个方程得到

$$x+k*m≡a_k(mod\ b_n)$$

化简得到$k*m≡a_k-x(mod\ b_n)$
x我们已经求出来的，所以只有一个未知数。
我们需要求的时最小解，所以我们用扩展欧几里得求出k。即可救出下一个方程的x。
若这个方程无解，则整个方程无解。
这就是全部的中国剩余定理

题目链接

模板

代码实现

#include<iostream>
#include<cstdio>
using namespace std;
#define fin(a,n) for(int i=a;i<=n;i++)
#define ll long long int
const int maxn=2e6+10;
ll a1[maxn],b1[maxn];
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得求数论逆元
{
	if(b==0)
	{
	x=1;
	y=0;
	return a;
	}
	ll gcd=exgcd(b,a%b,x,y);
	ll temp=x;
	x=y;
	y=temp-a/b*y;
	return gcd;
}
ll mul(ll a,ll b,ll mod)
{   ll res=0;
    while(b>0)
    {
	if(b&1)res=(res+a)%mod;
	a=(a+a)%mod;
	b>>=1;
   }
   return res;
}
ll exchi(int k)
{   ll a,b;
    scanf("%lld %lld",&a,&b);
	ll x,y;//x就是我们需要求出来的k，也就是最小正整数解
	ll M=a,ans=b;//M代表累乘，ans代表当前的x值 
	fin(2,k)
	{   ll a1,b1;
	    scanf("%lld %lld",&a1,&b1);
		ll a=M;
		ll b=a1;//ax+by=c; 
		ll c=(b1-ans%b+b)%b;
		ll gcd=exgcd(a,b,x,y),bg=b/gcd;
		if(c%gcd!=0)return -1;//无解情况
		x=mul(x,c/gcd,bg);//把x变为最小解，(x*c/gcd)% bg 
		ans=ans+x*M;
		M*=bg;//最小公倍数 
		ans=(ans%M+M)%M;
	}
	return (ans%M+M)%M;
}
int main()
{
	int n;
	scanf("%d",&n);
	ll tans=exchi(n);
	printf("%lld\n",tans);
	
}

上述代码已被一组数据hack，有时候会炸long long

5
998244353 469904850
998244389 856550978
998244391 656199240
998244407 51629743
998244431 642142204

下面记录sumijie大佬的代码

#include<iostream>
typedef __int128 ll;
using namespace std;
void exgcd(ll a,ll b,ll &g,ll &x,ll &y) {
    if (b == 0) {
        g = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,g,y,x);
    y-=(a/b)*x;
}
bool flag = false;
ll a1,a2,n1,n2;
ll abs(ll x) {
    return x>0?x:-x;
} 
void china() {
    ll d = a2 - a1;
    ll g,x,y;
    exgcd(n1,n2,g,x,y);
    if (d % g == 0) {
        x = ((x*d/g)%(n2/g)+(n2/g))%(n2/g);
        a1 = x*n1 + a1;
        n1 = (n1*n2)/g;
    }
    else 
        flag = true;
}
int n;
long long as[100001];
long long ns[100001];
ll realchina() {
    a1 = as[0];
    n1 = ns[0];
    for (ll i = 1;i<n;i++) {
        a2 = as[i];
        n2 = ns[i];
        china();
        if (flag)
            return -1;
    }
    return a1;
}

int main() { 
    cin>>n;
    flag = false;
    for (ll i = 0;i<n;i++)
        cin>>ns[i]>>as[i];
   ll tans = realchina();
}