欧几里得相关算法【含万能欧几里得】

技术分享 1年前 (2025-01-30) 0 999+

关注

前言

本文将介绍几个和欧几里得算法算法相关的算法，它们都使用了辗转相除的计算策略，获得类似于 (O(log V))（(V) 为值域）的优秀复杂度。

本文将提供清晰的（数学公式用 (LaTeX) 呈现的）伪代码。

约定

对于整数 (x,y)，定义 (z=xbmod y)，当且仅当 (z) 是最小的非负整数，满足 (ymid (x-z))。中间一竖是整除符号。

求最大公约数

问题：给定正整数 (x,yleq V)，求 (gcd(x,y))。（(gcd(x,y)) 表示 (x) 和 (y) 的最大公约数）

解说：若 (x=y)，则平凡地，(gcd(x,y)=x)。不妨设 (x<y)，则显然有 (gcd(x,y)=gcd(y-x,x))，根据取模的定义，可得 (gcd(x,y)=gcd(ybmod x,x))，于是就有做法了。

伪代码：（函数的返回值即为答案）

function (text{solve}(x,y))
- if (x=0) then
  - return (y)
- return (text{solve}(ybmod x,x))

复杂度分析：设时间复杂度为 (mathcal{T}(x,y))，现在我们证明如下命题：

(displaystyleexists x',y'in mathbb N^+,x'leq frac{x}{2},y'leq y)，满足 (mathcal{T}(x,y)leq mathcal{T}(x',y')+O(1))。

如果该命题成立，就容易推出 (mathcal{T}(x,y)=O(log V)) 了。

不妨设 (r=ybmod x)，则分两种情况讨论。

若 (displaystyle rleqfrac{x}{2})，根据算法过程，(mathcal{T}(x,y)=mathcal{T}(x,r)+O(1)=mathcal{T}(r,x)+O(1))，命题成立。
若 (displaystyle r>frac{x}{2})，则有 (mathcal{T}(x,y)=mathcal{T}(r,x)+O(1)=mathcal{T}(xbmod r,x)+O(1))，此时 (displaystyle xbmod r=x-rleqfrac{x}{2})，故命题成立。

于是，该算法的复杂度为

[boxed{O(log V)} ]

之后算法的复杂度都与它类似，将不再证明。

扩展欧几里得

问题：给定正整数 (a,bleq V)，请求出关于 ((x,y)) 的方程

[ax+by=1 ]

的任意整数解（即满足 (x,yinmathbb{Z})），保证有整数解。

解说：当 (a=b) 是，方程无整数解，所以不妨设 (a<b)。直接将 (b) 写成带余除法形式

[begin{gathered} k=lfloorfrac{b}{a}rfloor\ r=(bbmod a)\ b=ka+r end{gathered} ]

将 (b=ka+r) 代入方程，整理得

[ry+a(x+ky)=1 ]

可以将其看做关于 ((y,x+ky)) 的方程，这样，原本的系数为 (displaystyleleft[begin{matrix}a\ bend{matrix}right]) 的问题就能转化为系数为 (displaystyleleft[begin{matrix}r\ aend{matrix}right]) 的问题。这样，算法就呼之欲出了。

伪代码：

function (text{solve}(a,b))
- if (a=0) then
  - return ((0,1))
- let ((x',y')= text{solve}(bbmod a,a))
- return (displaystyle (y'-lfloorfrac{b}{a}rfloortimes x',x'))

复杂度分析：与欧几里得算法一样，(O(log V))。

生长：如果想要更详细的了解该算法，参见裴蜀定理 - OI Wiki。

线性同余不等式约束下的最小值

问题：给定正整数 (a,m)（(a<m)）和非负整数 (Lleq R<m)，请求出最小的非负整数 (x) 使得

[Lleq axbmod mleq R ]

若不存在这样的 (x)，需要报告无解。

解说：如果 ([L,R]) 中有 (a) 的倍数，即满足 (displaystyle atimeslceilfrac{L}{a}rceilleq R) 时，(x) 显然为 (displaystylelceilfrac{L}{a}rceil)。

在其他情况下，不妨将问题转化，再添加一个变量 (k)，问题变为：找到最小的非负整数 (k)，使得存在非负整数 (x)，满足

[Lleq ax-kmleq R ]

因为这里的 (k) 相当于 (displaystylelfloorfrac{ax}{m}rfloor)，所以当 (k) 最小时，(x) 可以取到最小的 (displaystyle lceilfrac{L+km}{a}rceil)。

变形可得，存在 (x) 满足上述不等式，当且仅当

[(-R)bmod aleq mkbmod aleq (-L)bmod a ]

其中 (mkbmod a=(mbmod a)kbmod a)。

所以算法就呼之欲出了。

伪代码：

function (text{solve}(a,m,L,R))
- if (L=0) then
  - return (0)
- if (a=0) or (R<L) then
  - return 无解
- if (displaystyle atimeslceilfrac{L}{a}rceilleq R) then
  - return (displaystylelceilfrac{L}{a}rceil)
- let (k=text{solve}(mbmod a,a,(-R)bmod a,(-L)bmod a))
- if (k=) 无解 then
  - return 无解
- return (displaystylelceilfrac{L+km}{a}rceil)

时间复杂度：同样是 (O(log V))。

帮助：你可能需要这个式子 (displaystylelceilfrac{x}{y}rceil=lfloorfrac{x+y-1}{y}rfloor)（当 (x,yin mathbb{Z},y>0) 时成立）。

类欧几里得

问题：给定非负整数 (n,a,b,cleq V)，满足 (cneq 0)，求

[sum_{i=0}^nleftlfloorfrac{ai+b}{c}rightrfloor ]

解决：不妨设答案为 (f(a,n,b,c))，则当 (a=0) 时，有

[f(a,n,b,c)=lfloorfrac{b}{c}rfloorcdot (n+1) ]

当 (ageq c) 或 (bgeq c) 时，有

[begin{gathered} f(a,b,c,n)=sum_{i=0}^nleftlfloorfrac{ai+b}{c}rightrfloor\ =sum_{i=0}^nleftlfloorfrac{(abmod c)i+(bbmod c)}{c}rightrfloor+lfloorfrac{a}{c}rfloor cdotfrac{n(n+1)}{2}+lfloorfrac{b}{c}rfloorcdot (n+1)\ =f(abmod c,bbmod c,c,n)+lfloorfrac{a}{c}rfloor cdot frac{n(n+1)}{2}+lfloorfrac{b}{c}rfloorcdot (n+1) end{gathered} ]

当 (a<c) 且 (b<c) 时，有（不妨设 (displaystyle m=leftlfloorfrac{an+b}{c}rightrfloor)）

[begin{gathered} f(a,b,c,n)=sum_{i=0}^nleftlfloorfrac{ai+b}{c}rightrfloor\ =sum_{i=0}^nsum_{j=0}^{m-1} [c(j+1)leq ai+b]\ =sum_{j=0}^{m-1}sum_{i=0}^n [ai> cj+c-b-1]\ =sum_{j=0}^{m-1}left(n-leftlfloorfrac{cj+c-b-1}{a}rightrfloorright)\ =mn-sum_{j=0}^{m-1}leftlfloorfrac{cj+c-b-1}{a}rightrfloor\ =mn-f(c,c-b-1,a,m-1) end{gathered} ]

然后就有做法了。

伪代码：

function (text{solve}(a,b,c,n))
- if (n=0) then
  - return (displaystyle lfloorfrac{b}{c}rfloor)
- if (ageq c) or (bgeq c) then
  - return (displaystyle text{solve}(abmod c,bbmod c,c,n)+lfloorfrac{a}{c}rfloor cdot frac{n(n+1)}{2}+lfloorfrac{b}{c}rfloorcdot (n+1))
- let (displaystyle m=leftlfloorfrac{an+b}{c}rightrfloor)
- if (m=0) then ^[1]
  - return (0)
- return (mn-text{solve}(c,c-b-1,a,m-1))

复杂度分析：为 (O(log V))。

万能欧几里得

约定：在本节中，部分运算将在群 (G) 下进行，所有的乘法运算都可能被看做 (G) 的群乘法。

问题：给定群元 (e,r,sin G)，其中 (e) 为单位元，给定函数（其中 (a,b,cinmathbb{N},cneq 0)）

[xi(x)=frac{ax+b}{c} ]

函数 (f: mathbb{N}to G) 的定义见下方伪代码。给定非负整数 (nleq V)，请求出 (f(n)) 的值。

下方伪代码中，(epsilon) 为无穷小的正数。

function (f(n))
- let (x=epsilon), (text{ans}=e)
- while (xleq n) do
  - if (xi(x)inmathbb Z) then
    - (text{ans}gets text{ans}times r)
  - if (xinmathbb Z) then
    - (text{ans}gets text{ans}times s)
  - (xgets x+epsilon)
- return (text{ans})

假设群 (G) 的乘法能做到单次 (O(T)) 的复杂度。

解说：当 (n=0) 时，平凡的，(f(0)=e)。

不妨设答案为 (g(a,b,c,n,r,s))。

容易发现，把 (xi) 所代表的的直线向下平移是没有影响的，即

[g(a,b,c,n,r,s)=g(a,bbmod c,c,n,r,s) ]

这里不妨设 (b<c)。

当 (ageq c) 时，尝试让一方模另一方。根据 (f) 差分的周期性，有：

[g(a,b,c,n,r,s)=g(abmod c,b,c,n,r,r^{lfloorfrac{a}{c}rfloor} times s) ]

可以使用 (f) 的几何意义直观理解该式。可以把 (f) 看成一条欧氏平面中的直线，是否乘 (r) 或 (s) 取决于直线上某点的纵坐标或横坐标是否是整数。发现每次给 (text{ans}) 乘上 (s) 前先至少要乘 (displaystyle lfloorfrac{a}{c}rfloor) 个 (r)。

当 (a<c) 时，尝试交换它们。

考虑直接将 (text{ans}) 写成求积形式，有

[text{ans}=prod_{i=1}^n r^{lfloorxi(i)rfloor-lfloorxi(i-1)rfloor}times s ]

为了方便研究，用字符串表示群元，群乘法表示为字符串的拼接，设 (e) 为空字符串，(r=texttt{r})，(s=texttt{s})，则 (text{ans}) 为一个由 (texttt{r}) 和 (texttt{s}) 构成的字符串。

比较显然的是，(text{ans}) 中，第 (i) 个 (texttt{s}) 前有 (lfloorxi(i)rfloor) 个 (texttt{r})。为了达到交换效果，我们不妨计算 (text{ans}) 中，第 (j) 个 (texttt{r}) 前面有几个 (texttt{s})。容易列出式子，答案为下方不等式中，整数 (t) 的最大值。

[leftlfloorfrac{at+b}{c}rightrfloor<j ]

它是

[frac{at+b}{c}<j ]

解不等式得 (t) 的最大值为

[leftlfloorfrac{c(j-1)+c-b-1}{a}rightrfloor ]

不妨设函数 (displaystyle xi'(x)=frac{cx+c-b-1}{a})。

于是 (text{ans}) 可以被表示为（不妨设 (m=lfloorxi(n)rfloor)）

[begin{gathered} text{ans}=s^{lfloorxi'(1-1)rfloor}times rtimesleft(prod_{j=2}^{m} s^{lfloorxi'(j-1)rfloor-lfloorxi'((j-1)-1)rfloor} times rright) times s^{n-lfloorxi'(m-1)rfloor}\ =s^{lfloorxi'(0)rfloor}times rtimes left(prod_{j=1}^{m-1}s^{lfloorxi'(j)rfloor-lfloorxi'(j-1)rfloor} times rright)times s^{n-lfloorxi'(m-1)rfloor}\ =s^{leftlfloorfrac{c-b-1}{a}rightrfloor}times rtimes g(c,c-b-1,a,m-1,s,r)times s^{n-lfloorxi'(m-1)rfloor}\ =s^{leftlfloorfrac{c-b-1}{a}rightrfloor}times rtimes g(c,(c-b-1)bmod a,a,m-1,s,r)times s^{n-leftlfloorfrac{cm-b-1}{a}rightrfloor}\ end{gathered} ]

然后就有做法了。

伪代码：

function (text{solve}(a,b,c,n,r,s))
- if (n=0) then
  - return (e)
- if (ageq c) or (bgeq c) then
  - return (text{solve}(abmod c,bbmod c,c,n,r,r^{lfloorfrac{a}{c}rfloor}times s))
- let (displaystyle m=leftlfloorfrac{an+b}{c}rightrfloor)
- if (m=0) then
  - return (s^n)
- return (s^{leftlfloorfrac{c-b-1}{a}rightrfloor}times rtimes g(c,(c-b-1)bmod a,a,m-1,s,r)times s^{n-leftlfloorfrac{cm-b-1}{a}rightrfloor})