gcd与类欧几里得

本文整理一下欧几里得算法和一些能用类欧解决的式子。

欧几里得算法与辗转相除

如何求两个数的gcd?

$gcd(x, y) = gcd(x - y, y)$

如果$d=gcd(x, y)$，那么$d|x,d|y,d|(x-y)$，我们把他们相减之后这个因子依然存在，但是倍数变小了。
一直这样往下做，我们最后可以把那个较小的数字变成$d$的一倍，也就是求出了$gcd(x,y)$。

复杂度

每次较大的数字至少会缩小一半，所以复杂度$\log$级别。

exgcd

线性方程组求解

$$ax+by=gcd(a, b)$$

求$x,y$。

$$ax+by=gcd(a, b)$$ $$b x_{1} + (a \% b) y_{1} = gcd(a, b).$$ $$b x_{1} + (a - b \times \left \lfloor \frac{a}{b} \right \rfloor ) y_{1}$$ $$= gcd(a, b).$$ $$a y_{1} + b (x_{1} - \left \lfloor \frac{a}{b} \right \rfloor y_{1} ) = a x + b y.$$

那么有

$$x = y_{1}.$$ $$y = x_{1} - \left \lfloor \frac{a}{b} \right \rfloor y_{1}.$$

void exgcd(ll a, ll b, ll& x, ll& y, ll& c)
{
	if(!b) {y = 0; x = 1; c = a; return;}
	exgcd(b, a % b, y, x); y -= a / b * x;
}

类欧

常见的类欧式子有三种。分别做出一点证明。

$f$

$$f(a, b, c, n) = \sum_{i=0}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor.$$

若$a \geq c$或$b \geq c$

$$f(a, b, c, n) = \sum_{i=0}^{n} \left \lfloor \frac{(a \% c) i + (b \% c)}{c} \right \rfloor + \left \lfloor \frac{a}{c} \right \rfloor i + \left \lfloor \frac{b}{c} \right \rfloor.$$ $$=f(a \% c, b \% c, c, n) + \left \lfloor \frac{a}{c} \right \rfloor \frac{n(n+1)}{2} + \left \lfloor \frac{b}{c} \right \rfloor (n+1).$$

若$a < c$且$b < c$

$$f(a, b, c, n) = \sum_{i=0}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor$$ $$= \sum_{i=0}^{n} \sum_{j=1}^{\left \lfloor \frac{an+b}{c} \right \rfloor} [j \leq \left \lfloor \frac{ai+b}{c} \right \rfloor]$$ $$= \sum_{j=1}^{\left \lfloor \frac{an+b}{c} \right \rfloor} \sum_{i=0}^{n} [j \times c - b \leq ai]$$ $$= \sum_{j=1}^{\left \lfloor \frac{an+b}{c} \right \rfloor} \sum_{i=0}^{n} [\left \lfloor \frac{jc-b-1}{a} \right \rfloor < i]$$ $$= \sum_{j=1}^{\left \lfloor \frac{an+b}{c} \right \rfloor} (n- \left \lfloor \frac{jc-b-1}{a} \right \rfloor)$$ $$= \left \lfloor \frac{an+b}{c} \right \rfloor n - \sum_{j=1}^{\left \lfloor \frac{an+b}{c} \right \rfloor} \left \lfloor \frac{jc-b-1}{a} \right \rfloor$$ $$= \left \lfloor \frac{an+b}{c} \right \rfloor n - \sum_{i=0}^{\left \lfloor \frac{an+b}{c} \right \rfloor - 1} \left \lfloor \frac{ic+(c-b-1)}{a} \right \rfloor$$ $$= \left \lfloor \frac{an+b}{c} \right \rfloor n - f(c, c - b - 1, a, \left \lfloor \frac{an+b}{c} \right \rfloor - 1).$$

$g$

$$g(a, b, c, n) = \sum_{i=0}^{n} i \left \lfloor \frac{ai+b}{c} \right \rfloor$$

如果$a \geq c$或$b \geq c$

$$g(a, b, c, n) = \sum_{i=0}^{n} i \left \lfloor \frac{(a \% c)i+(b \% c)}{c} + \frac{a}{c}i + \frac{b}{c} \right \rfloor$$ $$= \sum_{i=0}^{n} i \left \lfloor \frac{(a \% c)i + (b \% c)}{c} \right \rfloor + \left \lfloor \frac{a}{c} \right \rfloor i^2 + \left \lfloor \frac{b}{c} \right \rfloor i$$ $$= g(a \% c, b \% c, c, n) + \left \lfloor \frac{a}{c} \right \rfloor \frac{n(n+1)(2n+1)}{6} + \left \lfloor \frac{b}{c} \right \rfloor \frac{n(n+1)}{2}.$$

否则

$$g(a, b, c, n) = \sum_{i=0}^{n} i \left \lfloor \frac{ai+b}{c} \right \rfloor$$

令$m = \left \lfloor \frac{an+b}{c} \right \rfloor$

$$g(a, b, c, n) = \sum_{i=0}^{n}i \sum_{j=1}^{m} [\left \lfloor \frac{ai+b}{c} \right \rfloor \geq j]$$ $$= \sum_{j=1}^{m} \sum_{i=1}^{n} i [\left \lfloor \frac{jc-b-1}{a} \right \rfloor \leq i]$$ $$= \frac{1}{2} ((n+1)nm - f(c, c - b - 1, a, m - 1) - h(c, c - b - 1, a, m - 1)).$$