省选NOI-专题[数论][excrt][exgcd]：P4777 【模板】扩展中国剩余定理（EXCRT）

· · 题解

我这里推荐一下我的博客

在博客里观看更美观哦~

题目

华丽的分割线

解析

本题解由欧几里得求gcd和同余的性质去推导exgcd,crt,excrt

同余方程及性质

形如ax\equiv b \ (mod \ p)的式子称为同余方程,有如下性质

若a\equiv b \ (mod \ p)\ \ c\equiv d \ (mod \ p)\ 则\ ac\equiv bd \ (mod \ p)

对于一个同余方程\ ax\equiv b \ (mod \ p)\ 可化为\ ax=b+k*p

则\ ax-kp=b\ ,其中k,x为未知数,这就是二元一次不定方程

扩展欧几里得

对于\ ax+by=c\ ,a\ b\ c\ 已知,当且仅当gcd(a,b)\mid c,方程有整数解

只要解决\ ax+by=gcd(a,b)\ ,则x,y分别乘\frac{c}{gcd(a,b)}即可

因为\ gcd(a,b)=gcd(b,a\ mod\ b)\ ,所以我们要找出

因为$(a\ mod\ b)=(a-\lfloor\frac{a}{b}\rfloor*b)$,所以把这带进去,系数分一下类,可得 $\ ay_0+b*(x_0-\lfloor\frac{a}{b}\rfloor*b*y_0)=gcd(b,a\ mod\ b)\

可得到\begin{cases}x=y_0\\y= x_0-\lfloor\frac{a}{b}\rfloor*b*y_0\end{cases} 当b=0时,x=1,y=0,gcd(a,b)=a

递归即可求出不定方程的一组整数解,也就求出了同余方程的一个解

方程的通解

已知x_0\ y_0一组特解,如何求出方程所有解

设x_0+c\quad y_0-d也是一组解,求出最小的c和d,每次x_0+kc\ y_0-kd即可得到通解

则有ax_0+ac+by_0-bd=ax_0+by_0,则ac=bd=lcm(a,b)

因为ac=bd,二者均为a,b的倍数,且要求c,d最小,则为最小公倍数

则ac=bd=\frac{ab}{gcd(a,b)},解得c=\frac{b}{gcd(a,b)}\ d=\frac{a}{gcd(a,b)}

所以方程通解为\begin{cases}x=x_0+k*\frac{b}{gcd(a,b)}\\y=y_0-k*\frac{a}{gcd(a,b)}\end{cases}\quad 其中k为任意整数

我再提一下对于x\ mod\ p,把结果控制在0~p-1范围中需要

### 中国剩余定理 对于同余方程组$\begin{cases}x\equiv a_1(mod\ m_1)\\\qquad\vdots \\ x\equiv a_k(mod\ m_k)\end{cases}\ \ $当$m_1\dots m_k$两两互质时 可以用中国剩余定理解决,我们先构造一些东西 设$M=\prod_{i=1}^{k}m_i,\frac{M}{m_i}t_i\equiv1(mod\ m_i),t_i$为最小正整数解 $t_i$可用exgcd求出,则根据同余性质,$a_i*\frac{M}{m_i}t_i\equiv a_i(mod\ m_i)

则对于同余方程组的解x=\sum_{i=1}^{k}a_i*\frac{M}{m_i}t_i\qquadWHY?

因为对于任意模数m_i,和中除第i项,模m_i均为0,因为M中含有m_i这个因子

但在第i项时M/=m_i,且模数两两互素,所以M中不含因子m_i,且余数为a_i

则方程最小正整数解为((x\ mod\ M)+M)\ mod\ M\ 复杂度为O(nlogn)

扩展中国剩余定理

当m_1\dots m_k两两不互质时,便是我们的题目

设我们把前k-1个方程合并为一个方程,则

\begin{cases}x\equiv A(mod\ M)\\ x\equiv a_k(mod\ m_k)\end{cases}\ \ =\ \ \begin{cases}x=A+t_1*M\\ x=a_k+t_2*m_k\end{cases}\ \

两式相减得0=A-a_k+t_1*M-t_2*m_k

设$e=a_k-A,d=gcd(M,m_k)$,则$x_0*\frac{e}{d}*M-y_0*\frac{e}{d}*m_k=d*\frac{e}{d}

则t_1=x_0*\frac{e}{d},则x=A+t_1*M

所以合并之后模数为lcm(M,m_k),答案为A+t_1*M

2个变一个,3个变一个,以此类推,将k个方程合为一个方程

模数处理

对于上述t_1，不一定是最小正整数解,通解为t_1=x_0*\frac{e}{d}+k*\frac{m_k}{d}

则t_1=((t_1\ mod\ \frac{m_k}{d})+\frac{m_k}{d})\ mod\ \frac{m_k}{d}

对于新的答案,应用新模数lcm(M,m_k)去对A+t_1*M进行和t_1类似的操作

在乘法运算中会爆longlong,应使用快速乘龟速乘

代码

#include<cstdio>
#define ll long long
using namespace std;
void read(int &x)
{
    x=0;
    int f;
    f=1;
    char c;
    c=getchar();
    while((c<'0'||c>'9')&&c!='-')
    {
        c=getchar();
    }
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    x=x*f;
}
void read(ll &x)
{
    x=0;
    ll f;
    f=1;
    char c;
    c=getchar();
    while((c<'0'||c>'9')&&c!='-')
    {
        c=getchar();
    }
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    x=x*f;
}
ll mul(ll a,ll b,ll p)
{
    ll ans=0,x=a;
    while(b!=0)
    {
        if(b&1)
        {
            ans=(ans+x)%p;
        }
        x=(x+x)%p;
        b>>=1;
    }
    return (ans%p+p)%p;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        ll d;
        d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;   
    }
}
ll a[110000],m[110000];
int main()
{
    int n,i;
    read(n);
    for(i=1;i<=n;i++)
    {
        read(m[i]);
        read(a[i]);
    }
    ll M=m[1],ans=a[1];
    for(i=2;i<=n;i++)
    {
        ll e,x,d,y,nowm,newm;
        e=a[i]-ans;
        d=exgcd(M,m[i],x,y);
        nowm=m[i]/d;
        x=(x%nowm+nowm)%nowm;
        x=(mul(x,((e/d)%nowm+nowm)%nowm,nowm)+nowm)%nowm;
        newm=M*nowm;
        ans=(ans+mul(x,M,newm)+newm)%newm;
        M=newm;
    }
    printf("%lld",ans);
}