同余

大概是刚学会用 $\LaTeX$ 和 markdown 然后敲上瘾了，于是出现了第二篇 blog，也许之后就再也不想写笔记了（逃
也许会时不时补充知识点…
好像离自己抄代码的本意越来越远了

基础知识

• 定义： 若整数 $a$ 与整数 $b$ 除以正整数 $m$ 的余数相同，则称 $a,b$ 模 $m$ 同余，记为 $a\equiv b \pmod m$。这意味着$a-b=m\cdot k\ \ (k\in \mathbb Z)$

• 性质

  以下结论针对 $a,b,c,d \in \mathbb Z$ 和 $m,n\in \mathbb N$，对模 $m$ 同余的性质

  1. 对称性：$若a\equiv b\pmod m，则b\equiv a\pmod m$

  2. 传递性：$若a\equiv b\pmod m,b\equiv c\pmod m，则a\equiv c\pmod m$

  3. 运算法则（同余不满足除法）

     • $若a\equiv b\pmod m，则a+c\equiv b+c\pmod m$

     • $若a\equiv b\pmod m，则ac\equiv bc\pmod m$

     • $若a\equiv b\pmod m，c\equiv d\pmod m，则ac\equiv bd\pmod m$

     • $若a\equiv b\pmod m，则a^n\equiv b^n\pmod m$

  4. 取模运算

     • $ab \bmod k=(a \bmod k)(b\bmod k)\bmod k$

     • $(a+b)\bmod k=(a\bmod k+b\bmod k)\bmod k$

     • $(a-b)\bmod k=(a\bmod k-b\bmod k+k)\bmod k$

     • $a^b\bmod k=(a\bmod k)^b\bmod k$

  5. $若a\bmod p=x，a\bmod q=x，且\ \ p,q\ \ 互质，则a\mod (p*q)=x$

• 费马小定理
  若 $p$ 为质数，$a\in \mathbb Z$ ，则 $a^p\equiv a\pmod p$

• 欧拉定理及其推论
  若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1\pmod n$

  对于 $\forall b\in \mathbb{N_+}$ ，有 $a^b\equiv a^{b\bmod \varphi(n)}\pmod n$

拓展欧几里得

• $B\acute ezout$ 定理
  对于 $\forall a,b\in \mathbb Z$，存在一对正整数 $x,y$ ，满足 $ax+by=\gcd(a,b)$

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11

  int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0;//x=1,y=0,b=0,ax+by=gcd(a,b) return a; } int d=exgcd(b,a%b,x,y); int z=x; x=y; y=z-y*(a/b); return d; }

  其中得到的结果 $x_0,y_0$ 仅为 $ax+by=\gcd(a,b)$ 的一组特解

  对于方程 $ax+by=c$ ，设 $\gcd(a,b)=d$ ，只有当 $d\mid c$ 时方程有解。该方程的一组特解为 $\cfrac{c}{d}x_0$，$\cfrac{c}{d}y_0$，方程的通解为

  $x=\frac{c}{d}x_0+\frac{b}{d}k，\quad y=\frac{c}{d}y_0-\frac{a}{d} k\,\ (k\in \mathbb{Z})$

乘法逆元

• 定义

  若整数 $b,m$ 互质，且满足 $b\mid a$,，则存在整数 $x$ ，使 $\frac{a}{b}\equiv ax\pmod x$ ，称 $x$ 为 $b$ 的模 $m$ 的乘法逆元，记为 $b^{-1}\pmod m$
  可得 $b\cdot b^{-1}\equiv 1\pmod m$

• 快速幂求逆元

  由费马小定理可得，若 $m$ 为质数，则有

  $b^m\equiv b\pmod m\Rightarrow b^m\cdot b^{-1}\equiv 1\pmod m \\ \quad \\ \Rightarrow b^{m-2}\cdot b\equiv 1\pmod m$

  可得 $b^{m-2}$ 为逆元

  1 2 3 4 5 6 7 8 9

  int quim(int a,int x,int mod){ int ans=1; while(x){ if(x&1) ans=ans*a%mod; a=a*a%mod; x>>=1; } return ans; }

• 拓展欧几里得求逆元

  只保证 $b,m$ 互质，可通过求解线性同余方程 $b\cdot x\equiv 1\pmod m$得到逆元

  $b\cdot x\equiv 1\pmod m\Rightarrow bx=-ym+1\Rightarrow\\ \quad \\ bx+ym=1\,\ (y\in \mathbb Z)$

  用拓展欧几里得算法解出 $x$ 即可

• 线性求逆元

  首先我们有 $1^{-1}\equiv 1\pmod p$ ，设 $p=ki*r\,\ (1<r<i<p)$ ，其中 $k$ 为 $p/i$ 的商，$r$ 为余数 ,可得 $k=\lfloor \cfrac{p}{i}\rfloor$ ， $r=p\bmod i$

  $ki+r\equiv 0\pmod p \Rightarrow k\cdot r^{-1}+i^{-1}\equiv 0\cdot r^{-1}\cdot i^{-1}\pmod p\Rightarrow \\ \quad \\ i^{-1}\equiv -k\cdot r^{-1}\pmod p$

  代入 $k,r$ 得

  $i^{-1}\equiv -\lfloor \cfrac{p}{i}\rfloor \cdot (p\bmod i)\pmod p$

  代码如下

  1 2 3 4 5 6

  void get_inv(int p){//1~p中(mod p)情况下的逆元 inv[1]=1; for(int i=2;i<p;i++){ inv[i]=(p-p/i)*inv[p%i]%p; } }

线性同余方程

• 概念

  设 $a,b,m\in \mathbb Z$ ，求一个整数 $x$ 满足 $ax\equiv b\pmod m$。

  $ax\equiv b\pmod m\Rightarrow ax=b-ym\Rightarrow\\ \quad \\ ax+ym=b\,\ (y\in \mathbb Z)$

  设 $d=\gcd(a,m)$ ，由$B\acute ezout$ 定理可得，只有当 $d\mid b$ 时，方程有解，此时可用 拓展欧几里得算法 先解出方程 $ax_0+my_0=d$ 的解 $x_0,y_0$ ，可得 $x$的通解为

  $x=\frac{b}{d}x_0+\frac{m}{d}k\,\ (k\in\mathbb Z)$

中国剩余定理(CRT)

设 $m_1,m_2,\cdots,m_n$ 是两两互质的整数，设 $m=\displaystyle\prod_{i=1}^n{m_i}，M_i=\frac{m}{m_i}，x_i$ 是方程 $M_{i}x_i \equiv 1\pmod m$ 的一个解。对于任意 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ，方程组

$\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \quad \quad \quad \vdots \\ x\equiv a_n\pmod {m_n} \end{cases}$

的一个整数解为 $x=\displaystyle\sum_{i=1}^n{a_i M_i x_i}$ ，通解可表示为 $x+km\,\ (k\in\mathbb Z)$

代码如下

1
2
3
4
5
6
7
8
9
10

for(int i=1;i<=k;i++){
    scanf("%d%d",&m[i],&a[i]);
    M*=m[i];//预处理 M
}
for(int i=1;i<=k;i++){
    mx=M/m[i];
    exgcd(mx,m[i],x,y);//调用拓展欧几里得
    if(x<0) x+=m[i];
    n+=a[i]*mx*x;//n 为结果
}

拓展中国剩余定理

若上式的$m_1,m_2,\cdots,m_n$ 不满足两两互质，我们就需要两两合并线性同余方程。方程组

$\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \end{cases} \Leftrightarrow x=k_1 m_1+a_1=k_2m_2+a_2\,\ (k_1,k_2\in\mathbb Z)\Rightarrow \\ \quad \\ k_1m_1-k_2m_2=a_2-a_1$

然后就可以判断是否有解了，设 $d=\gcd(m_1,m_2)$ ，若 $d\mid(a_2-a_1)$ ，则方程有解。但此时无法解出准确的 $k_1,k_2$ ，还需要继续处理。
设 $p_1=\cfrac{m_1}{d}\,\ ,p_2=\cfrac{m_2}{d}$ ，则有方程

$k_1p_1-k_2p_2=\frac{a_2-a_1}{d}$

显然 $\gcd(p_1,p_2)=1$ 。解出方程 $f_1p_1-f_2p_2=1$ 的特解 $f_1,f_2$ ，乘上 $\cfrac{a_2-a_1}{d}$ 可得原方程，解出特解

$\begin{cases} k_1=\cfrac{a_2-a_1}{d} f_1\\ k_2=-\cfrac{a_2-a_1}{d}f_2 \end{cases}\\ \quad \\ 代入得到特解\,\ x_0=a_1+\cfrac{a_2-a_1}{d} f_1m_1$

通解为 $x=x_0+k\cdot lcm(m_1,m_2)\,\ (k\in \mathbb Z)$

设最小非负整数解为 $x_m$ ，合并后的方程为

$x\equiv x_m\pmod {lcm(m_1,m_2)}$

最终当合并到只剩一个方程时，$x_m$ 即为满足方程组的最小非负整数

代码如下

1
2
3
4
5
6
7
8
9
10
11
12

bool exCRT(){
    m=b[1],ans=a[1];
    for(int i=2;i<=n;i++){
        ll d=gcd(m,b[i]);
        if((a[i]-ans)%d!=0) return false;//无解
        ll l=lcm(m,b[i]);
        exgcd(m/d,b[i]/d,x,y);
        ans=(ans+(a[i]-ans)/d*x*m%l+l)%l;
        m=l;
    }
    return true;
}

END