标签：方程 frac gcd 欧几里得 扩展 笔记 ax cases 正整数

扩展欧几里得算法(exgcd)

简介

扩展欧几里得算法基于辗转相除法构建，主要用于求方程

\[ax+by=c \]

最小正整数解

步骤

1.求方程\(ax+by=gcd(a,b)\)的解

---

我们构造两个方程

\[\begin{cases} ax+by=gcd(a,b)\\ bx'+(a\%b)y'=gcd(b,a\%b) \end{cases}\]

因为由欧几里得算法易于得到

\[gcd(a,b)=gcd(b,a \%b) \]

所以

\[ax+by=bx'+(a\%b)y' \]

由此递推易得方程

\[ax+0y=1 \]

此时方程解为

\[x=\frac{1}{a} \]

对于\(a\%b\)我们可以表示为

\[a\%b=a-b*\lfloor \frac{a}{b} \rfloor \]

将此式带入原方程即可得

\[ax+by=bx'+ay'-b*\lfloor \frac{a}{b} \rfloor y' \]

整理可得

\[ax+by=ay'+b(x'-\lfloor \frac{a}{b} \rfloor y') \]

因为\(a=a,b=b\)
所以

\[\begin{cases} x=y'\\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{cases}\]

在写代码时可以用递归实现，先往下递归直到\(a\%b=0\)得到方程的一个解，然后返回利用x，y和x'，y'的关系得到原方程的解

2.求方程\(ax+by=gcd(a,b)\)的最小整数解

---

因为有方程\(ax+by=gcd(a,b)\)，所以

\[a(x+b/a)+b(y-a/b)=gcd(a,b) \]

显然\(x+b/a,y-a/b\)也为方程的一组解
此时，我们把

\[b/a,a/b \]

分别称为x，y的一个周期，一般用字母\(T\)表示
在步骤1里我们已经得到了方程的一个解\(x,y\)
因为

\[\begin{cases} x'=x+k*T1\\ y'=y+k*T2 \end{cases}\]

也为方程的一组解，所以

\[\begin{cases} x'=x\%T1\\ y'=y\%T2 \end{cases}\]

因为无法保证\(x,y\)同时都为正整数
所以对于\(x\)的最小正整数解为

\[x'=(x\%T1+T1)\%T1 \]

3.求普遍方程\(ax+by=c\)的最小正整数解

---

我们已经得到了普遍方城\(ax+by=gcd(a,b)\)的最小正整数解
我们设

\[p=c/gcd(a,b) \]

那么有

\[a*px+b*py=p*gcd(a,b) \]

对比系数易于得到，\(ax+by=c\)的对于\(x\)的最小正整数解为

\[\begin{cases} x'=px\\ y'=py \end{cases}\]

显然如果\(c\%gcd(a,b)!=0\)那么方程无最小正整数解

求逆元

对于求有理数的模运算

\[(\frac{a}{b})\%p \]

我们可以将其转化为

\[a\%p*(\frac{1}{b}\%p) \]

而\(\frac{1}{b}\%p\)就可以转化为求方程

\[ax\equiv1(\%p) \]

的解
因为\(1\%p=1\)，所以\(x\)就可以看做方程

\[ax+py=1 \]

最小正整数解，其中\(x\)被称为a的逆元
特别的如果\(p\)是一个质数，那么根据费马小定律

\[a^{p-1}\equiv1(\%p)\\ a*a^{p-2}\equiv1(\%p)\]

所以

\[x=a^{p-2} \]

标签：方程,frac,gcd,欧几里得,扩展,笔记,ax,cases,正整数
From： https://www.cnblogs.com/GSNforces/p/18417133