CRT 中国剩余定理

· · 个人记录

CRT 中国剩余定理

设 m_1,m_2,...,m_x 是两两互质的整数，M= \prod_{i=1}^{x} m_i ,M_i= \frac {M}{m_i}，t_i 是 M_it_i \equiv 1 \ ({\rm {mod}} \ m_i) 的一个解，对于任意的整数 a_1,a_2,...,a_x，方程组：

\begin{cases} x \equiv a_1 \ ({\rm {mod}} \ m_1) \\ x \equiv a_2 \ ({\rm {mod}} \ m_2) \\ ... \\ x \equiv a_x \ ({\rm {mod}} \ m_x) \\ \end{cases}

有整数解，解为 \sum_{i=1}^x a_iM_it_i 。

证明略 定理不就是用来背的吗

模版：

P1495 【模板】中国剩余定理(CRT)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lxl long long
using namespace std;

lxl a[15],b[15];
int n;

inline lxl exgcd(lxl a,lxl b,lxl &x,lxl &y)
{
    if(!b) {x=1,y=0;return a;}
    lxl k=exgcd(b,a%b,x,y);
    lxl z=x;x=y,y=z-a/b*y;
    return k;
}

inline lxl china()
{
    lxl M=1,ans=0;
    for(int i=1;i<=n;i++)
        M*=a[i];
    for(int i=1;i<=n;i++)
    {
        lxl tx,y,Mi=M/a[i];
        exgcd(Mi,a[i],tx,y);
        ans=(ans+b[i]*Mi*tx)%M;
    }
    return (ans+M)%M;
}

int main()
{
    //freopen("P1495.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]);
    printf("%lld\n",china());
    return 0;
}

exCRT 扩展中国剩余定理

说是中国剩余定理，但是好像和CRT关系不大。

扩展中国剩余定理就是合并线性同余方程式，解决 m_i 不互素的情况。

先考虑两个同余方程式：

\begin{cases} x \equiv a_1 ({\rm {mod}} \ b_1) \\ x \equiv a_2 ({\rm {mod}} \ b_2)\end{cases}\implies \begin{cases} x = a_1 +k_1 * b_1 \\ x \equiv a_2 + k_2 * b_2\end{cases}\implies a_1 +k_1 * b_1=a_2 + k_2 * b_2\implies k_1 * b_1+k_2 * b_2=a_2-a_1

如果不定方程有解，使用扩展欧几里德算法求出一个 k_1 的特解 k_0，则 x 的一个特解 x_0=a_1+k_0 * b_1。通解

k_i=k_0+u* \frac {b_2}{{\rm{gcd}}(b_1,b_2)},u \in {\rm{Z}}

则：

x=k_i * b_1 +a_1 =u * \frac {b_1b_2}{{\rm{gcd}}(b_1,b_2)}+a_1+k_0 * b_1 x=u * {\rm {lcm}}(b_1,b_2)+x_0 x \equiv x_0 \ ({\rm {mod}} \ {\rm {lcm}} (b_1,b_2))

于是就把两个同余方程式合并成了一个。同理，将所有方程式按此方法合并，答案为最后的 x_0。

模版：

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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lxl long long
#define maxn 100005
using namespace std;

inline lxl times(lxl a,lxl b,lxl mod)
{
    lxl ans=0;
    while(b>0)
    {
        if(b%2) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

inline lxl exgcd(lxl a,lxl b,lxl &x,lxl &y)
{
    if(!b) {x=1,y=0;return a;}
    lxl k=exgcd(b,a%b,x,y);
    lxl z=x;x=y,y=z-a/b*y;
    return k;
}

int n;
lxl a[maxn],b[maxn];

int main()
{
    //freopen("P4777.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
    lxl M=a[1],ans=b[1];
    for(int i=2;i<=n;i++)
    {
        lxl a1=M,a2=a[i],bi=(b[i]-ans%a2+a2)%a2,x,y;
        lxl g=exgcd(a1,a2,x,y);
        a2/=g,bi/=g;
        x=times(x,bi,a2);
        ans+=M*x;
        M*=a[i]/g;
        ans=(ans+M)%M;
    }
    printf("%lld\n",(ans+M)%M);
    return 0;
}