警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」exgcd - 数论

简介

数论只会 GCD 说的就是我了……

exgcd 可以解出形如 \(ax+by=\gcd(a,b)\) 的方程的一组解。

其实可以解出 \(\enclose{horizontalstrike}{ax+by=c}\),因为 \(\enclose{horizontalstrike}{c\ne\gcd(a,b)}\) 时无解

首先,当 \(b=0\) 时,显然可以得到一组解 \(x=1,y=0\)。此时 \(a\times1+0\times0=\gcd(a,0)\)

因为有 \(\gcd(a,b)=\gcd(b,a\bmod b)\),令 \(x,y\) 满足 \(bx+(a\bmod b)y=\gcd(b,a\bmod b)\),那么可得

\[ \begin{aligned} & \gcd(a,b) \\ = & \gcd(b,a\bmod b) \\ = & ~bx+(a\bmod b)y \\ = & ~bx+(a-b\lfloor a/b\rfloor)y \\ = & ~ay + b(x-\lfloor a/b\rfloor y) \\ \end{aligned} \]

所以令 \(x'=y,y'=x-\lfloor a/b\rfloor y\),那么显然 \(ax'+by'=\gcd(a,b)\)

应用

求线性同余方程

求出一个 \(x\),满足 \(ax\equiv b\pmod p\)

\[ \begin{aligned} ax & \equiv b\pmod p \\ ax-b & \equiv0\pmod p \\ ax+py & =b \\ ax+py & =t\cdot\gcd(a,p) \\ {\color{red}\text{let}}~ax_0+py_0 & =\gcd(a,p), \\ atx_0+pty_0 & =b \\ x &= tx_0 \\ x &= \frac{bx_0}{\gcd(a,p)}. \\ \end{aligned} \]

P1082 [NOIp2012]同余方程

题意

传送门:洛谷 P1082 - 同余方程

\(a\) 在模 \(b\) 意义下的逆元。保证有解。

解法 1

首先,如果 \(a\) 在模 \(b\) 意义下有逆元,那么 \(\gcd(a,b)=1\)

证明:因为有 \(ax\equiv1\pmod b \Longrightarrow b\mid(ax-1)\),可以考虑设一个 \(y\),使得 \(ax-1=-yb\)\(ax+by=1\)。这个方程的有解条件是 \(\gcd(a,b)\mid1\)\(\gcd(a,b)=1\)

所以只要解出 \(ax+by=1\) 就可以得到 \(a\) 的逆元。

注意到 \(a\) 可能解出负数,所以需要 (a + p) % p

代码 1

解法 2

……\(\gcd(a,b)=1\)

注意到欧拉定理的前提条件也是 \(\gcd(a,b)=1\),所以可以用欧拉定理求逆元。

欧拉定理(其 N):\(a^{\varphi(n)}\equiv1\pmod n,\quad\gcd(a,n)=1\)

所以逆元就是 \(a^{\varphi(n)-1}\)

然后只需要 \(O(\sqrt n)\) 求出 \(\varphi(n)\) 然后快速幂就好了。可惜比 exgcd 慢一点……

代码 2