当前位置：网站首页>模线性方程组（中国剩余定理+通用解法）

模线性方程组（中国剩余定理+通用解法）

2022-06-11 07:23:00 【CaptainHarryChen】

求解

⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ x \equiv a 1 (m o d m 1) x \equiv a 2 (m o d m 2) x \equiv a 3 (m o d m 3) . . . x \equiv a n (m o d m n)

$\begin{cases} x \equiv a_1\ (mod\ m_1)\\ x \equiv a_2\ (mod\ m_2)\\ x \equiv a_3\ (mod\ m_3)\\ ...\\ x \equiv a_n\ (mod\ m_n) \end{cases}$

中国剩余定理

若 $m_1,m_2,m_3,...,m_n$ 两两互质，则可用中国剩余定理

设 $M=\prod_{i=1}^n m_i$ ， $M_i=M/m_i$ ， $t_i$ 为 $M_i$ 在 $(mod\ m_i)$ 意义下的逆元，那么通解为

x = k M + \sum i = 1 n a i t i M i

$x=kM+\sum_{i=1}^n a_it_iM_i$
解释一下： ~~懒得证~~
因为

tiMi≡1 (mod mi) t i M i ≡ 1 ( m o d m i ) $t_iM_i \equiv 1\ (mod\ m_i)$ ，而

Mj≡0 (mod mi) (j≠i) M j ≡ 0 ( m o d m i ) ( j ≠ i ) $M_j\equiv 0\ (mod\ m_i)\ (j≠i)$ ，所以整个求和式子中，模

mi m i $m_i$ 有用的就只剩下

aitiMi≡ai (mod mi) a i t i M i ≡ a i ( m o d m i ) $a_it_iM_i\equiv a_i\ (mod\ m_i)$ ，对每一个

mi m i $m_i$ 都如此，满足所有条件。

通用解法

不要求 $m_1,m_2,m_3,...,m_n$ 两两互质的解法

首先考虑只有两个方程

{x \equiv a 1 (m o d m 1) x \equiv a 2 (m o d m 2)

$\begin{cases} x \equiv a_1\ (mod\ m_1)\\ x \equiv a_2\ (mod\ m_2)\\ \end{cases}$
则

{x = a 1 + m 1 k 1 x = a 2 + m 2 k 2

$\begin{cases} x = a_1+m_1k_1\\ x = a_2+m_2k_2\\ \end{cases}$

a 1 + m 1 k 1 = a 2 + m 2 k 2

$a_1+m_1k_1=a_2+m_2k_2$

m 1 k 1 - m 2 k 2 = a 2 - a 1

$m_1k_1-m_2k_2=a_2-a_1$
用exgcd求不定方程，将

k1 k 1 $k_1$ ，

k2 k 2 $k_2$ 解出，并带入原方程，得到一个特解

x x $x$
可知这两个方程的通解

X

$X$ 为

X = x + t \times l c m (m 1, m 2)

$X=x+t\times lcm(m_1,m_2)$
即

X \equiv x (m o d l c m (m 1, m 2))

$X\equiv x\ (mod\ lcm(m_1,m_2)\ )$

我们已经成功把两个方程合为一个，只需要继续把这个方程与方程组其他方程一一合并，就求出解了

模板题

HDU1573，求解的个数

#include<cstdio>
const int MAXM=13;
long long gcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    long long xx,yy,d=gcd(b,a%b,xx,yy);
    x=yy;
    y=xx-a/b*yy;
    return d;
}
long long a[MAXM],b[MAXM];
int main()
{
    int T,M;
    long long N,A,B,d,l,x,y,p,q,r;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%d",&N,&M);
        for(int i=1;i<=M;i++)
            scanf("%I64d",a+i);
        for(int i=1;i<=M;i++)
            scanf("%I64d",b+i);
        A=a[1];B=b[1];
        bool flag=true;
        for(int i=2;i<=M;i++)
        {
            p=A;q=a[i];r=b[i]-B;
            d=gcd(p,q,x,y);
            if(r%d)
            {flag=false;break;}
            p/=d;q/=d;r/=d;
            x=x*r;
            x=(x%q+q)%q;
            l=A/d*a[i];
            B=x*A+B;
            B=(B%l+l)%l;
            A=l;
            if(B>N)break;
        }
        if(flag&&B<=N)
            printf("%I64d\n",(N-B)/A+(B!=0));
        else
            puts("0");
    }
    return 0;
}