扩展中国剩余定理 exCRT 学习笔记

作者: wjyyy 分类: 中国剩余定理,学习笔记,数学 发布时间: 2019-03-20 14:48

点击量:159

前言

由于 $latex \{\mathrm{CRT}\}\subseteq\{\mathrm{exCRT}\}$,而且 CRT 又太抽象了,所以直接学 exCRT 了。

摘自 huyufeifei 博客

lbwtxdy

这么抽象的东西我怎么可能会写

前置技能

  • gcd/lcm
  • exgcd
  • 快速乘

参考资料

用途

用于求一个关于 $latex x$ 的同余方程组
$$
\left\{
\begin{matrix}
x\equiv a_1\pmod{b_1}\\
x\equiv a_2\pmod{b_2}\\
\cdots\\
x\equiv a_n\pmod{b_n}
\end{matrix}\right.
$$
的解。

解法推导

考虑到如果 $latex x$ 对原方程组成立,那么 $latex x$ 对其中任意几个方程也都成立。那么如果要满足 $latex x$ 对前 $latex i$ 个方程都成立,一个必要条件是对前 $latex i-1$ 个方程都成立。

采用一种类似“增量法”的思路来合并每个式子。

假定前 $latex i-1$ 个式子已经合并完了,得到 $latex x\equiv a_{i-1}\pmod{b_{i-1}}$。此时合并
$$
\left\{
\begin{aligned}
&x\equiv a_{i-1}&\pmod{b_{i-1}}\\
&x\equiv a_i&\pmod{b_i}
\end{aligned}\right.
$$
它的本质是存在 $latex k_1,k_2$,满足(上下颠倒了一下,方便下面推导)
$$
\left\{
\begin{aligned}
&x+k_1b_i=a_i\\
&x+k_2b_{i-1}=a_{i-1}
\end{aligned}\right.
$$
两式相减,得到
$$
k_1b_i-k_2b_{i-1}=a_i-a_{i-1}
$$
此时,仅有 $latex k_1,k_2$ 是变量,剩下的都已知。但是我们用 exgcd 解方程时,要求等式右边是 $latex \gcd(b_i,b_{i-1})$。此时我们列出一个新方程
$$
k_1’b_i+k_2’b_{i-1}=\gcd(b_i,b_{i-1})
$$
解出 $latex k_1’$ 的一个特解 $latex k_0$。

那么为了满足新方程和原方程都成立,那么
$$
\frac {k_1}{k_1′}=\frac{k_2}{k_2′}=\frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}
$$
因此 $latex k_1$ 有特解
$$
k_{1_0}=k_0\times \frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}
$$
则 $latex k_1$ 的通解是
$$
k_{1_0}+t\times \frac{b_{i-1}}{\gcd(b_i,b_{i-1})},\ t\in \mathbb Z
$$

不定方程的通解

对于 $latex ax+by=c$ 这个方程,假定我们已经解出来一组解为
$$
\left\{
\begin{matrix}
x=x_0\\
y=y_0
\end{matrix}
\right.
$$
我们带入后对左侧式子变形,得到 $latex ax_0+S+by_0-S=c$。

我们要从 $latex ax_0+S$ 中提一个 $latex a$ 出来,从 $latex by_0-S$ 中提一个 $latex b$ 出来,得到 $latex a(x_0+\frac Sa)+b(y_0-\frac Sb)=c$。

此时最小的满足 $latex x_0+\frac Sa,\ y_0-\frac Sb$ 都是整数的 $latex S$ 就是 $latex a,b$ 的最小公倍数了。

那么每个相邻的 $latex x$ 之间相差 $latex \frac Sa=\frac{\operatorname{lcm}(a,b)}a=\frac b{\gcd(a,b)}$,即 $latex x$ 的通解为 $latex x_0+t\times \frac b{\gcd(a,b)},\ t\in \mathbb Z$。

后面的式子仅与 $latex a,b$ 有关。

又因为
$$
x+k_1b_i=a_i
$$
我们带入 $latex k_1$ 的通解,得
$$
x+\left(k_{1_0}+t\times \frac{b_{i-1}}{\gcd(b_i,b_{i-1})}\right)\times b_i=a_i,\ t\in \mathbb Z
$$
化简
$$
x+b_ik_{1_0}+t\times \frac{b_ib_{i-1}}{\gcd(b_i,b_{i-1})}=a_i,\ t\in \mathbb Z\\
t\times\operatorname{lcm}(b_i,b_{i-1})=a_i-x-b_ik_{1_0},\ t\in \mathbb Z
$$
由于 $latex t\in \mathbb Z$,所以
$$
a_i-x-b_ik_{1_0}|\operatorname{lcm}(b_i,b_{i-1})\\
a_i-x-b_ik_{1_0}\equiv 0\pmod{\operatorname{lcm}(b_i,b_{i-1})}\\
x\equiv a_i-b_ik_{1_0}\pmod{\operatorname{lcm}(b_i,b_{i-1})}
$$
$latex \equiv$ 符号右边的都是已知量,这时我们就把两个方程结合到一块了。

我们依次合并 $latex (2)=[(1),(2)],(3)=[(2),(3)],\cdots,(n)=[(n-1),(n)]$,最终得到第 $latex n$ 个式子
$$
x\equiv a_n\pmod{\operatorname{lcm}(b_1,b_2,\cdots,b_m)}
$$
($latex a_n$ 是合并 $latex n-1$ 个式子后的新 $latex a_n$,上述过程中每一步都会更新 $latex a_i$)

此时 $latex a_n$ 就是解了,取模取正数就是最小正整数解。

(上下两部分实质相同)

解法简述

对于
$$
\left\{
\begin{aligned}
&x\equiv a_{i-1}&\pmod{b_{i-1}}\\
&x\equiv a_i&\pmod{b_i}
\end{aligned}\right.
$$

$$
\left\{
\begin{aligned}
&x+k_1b_i=a_i\\
&x+k_2b_{i-1}=a_{i-1}
\end{aligned}\right.
$$
解出
$$
k_1’b_i-k_2’b_{i-1}=\gcd(b_i,b_{i-1})
$$
的特解 $latex k_1’$,两边同乘 $latex \frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}$,得到
$$
k_1b_i-k_2b_{i-1}=a_i-a_{i-1}
$$
那么 $latex k_1’$ 也被乘了 $latex \frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}$,因此 $latex k_1$ 有特解
$$
k_{1_0}=k_1’\times \frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}
$$
而 $latex k_1$ 的通解是
$$
k_1=k_{1_0}+t\times\frac{b_{i-1}}{\gcd(b_i,b_{i-1})}
$$
代回去就是
$$
x+k_{1_0}b_i+t\times \operatorname{lcm}(b_i,b_{i-1})=a_i
$$
得到
$$
x\equiv a_i-k_{1_0}b_i\pmod{\operatorname{lcm}(b_i,b_{i-1})}
$$
作为第 $latex i$ 个方程即可。

注意事项

在 $latex k_1,k_{1_0},a_i$ 的计算中是有可能爆 long long 的,而这三个计算恰好又都是模意义下,所以使用快速乘。

一般情况下不考虑 $latex \operatorname{lcm}(b_1,b_2,\cdots,b_n)$ 爆 long long 的情况。

代码

#include<cstdio>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
ll qmul(ll x,ll y,ll p)
{
    ll ans=0,f=1;
    if(x<0)
    {
        x=-x;
        f=-f;
    }
    if(y<0)
    {
        y=-y;
        f=-f;
    }
    while(y)
    {
        if(y&1)
            ans=(ans+x)%p;
        x=(x+x)%p;
        y>>=1;
    }
    return ans*f;
}
ll a[100100],b[100100];
int main()
{
    int n;
    ll x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&b[i],&a[i]);
    for(int i=2;i<=n;++i)
    {
        ll g=exgcd(b[i],b[i-1],x,y);
        ll t=b[i-1]/g;//k1 的最小波动 Δ
        x=qmul(x,(a[i]-a[i-1])/g,t);
        x=(x%t+t)%t;
        a[i]-=qmul(x,b[i],b[i]/g*b[i-1]);
        b[i]=b[i]/g*b[i-1];
        a[i]=(a[i]%b[i]+b[i])%b[i];
    }
    printf("%lld\n",(a[n]%b[n]+b[n])%b[n]);
    return 0;
}

3
说点什么

avatar
3 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【exCRT学习笔记】 […]

trackback

… [Trackback]

[…] Read More Info here on that Topic: wjyyy.top/3375.html […]

/* */