欧几里得相关

i may change it in total

裴蜀定理

欧几里得算法

不断将两数规模变小,直到能直接判断解
依据:$gcd(a,b)=gcd(b,a$%$b),gcd(a,0)=a$
递归次数最多的是斐波那契数$f(n)$和$f(n-1)$

$O(logn)$

扩展欧几里得算法

记$d=gcd(a,b)$,求出$ax+by=d$的一组解$(x,y)$,保证满足$|x|+|y|$最小
其任意解为$(x+kb’,y-ka’)$,$a’=a/d$,$b’=b/d$,$k$取任意整数
对于一般的线性方程$ax+by=c$,若$!(d|c)$则无解,否则$x \times \frac{c}{d}$,$y \times \frac{c}{d}$即可

$O(logn)$

类欧几里得算法

形式1

$f(a,b,c,n)=\sum\limits_{i=0}^n \lfloor \frac{ai+b}{c}\rfloor$

当$a\geq c$或$b \geq c$时
$f(a,b,c,n)=$$\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a$%$c,b$%$c,c,n)$

当$a<c$且$b<c$时
令$m= \lfloor \frac{an+b}{c}\rfloor$
$f(a,b,c,n)=$$nm-f(c,c-b-1,a,m-1)$

推导

分享到: