扩展欧几里得算法 基础欧几里得算法可以用于求 a , b a,b a , b 的最大公因数:
1 2 3 int gcd (int a,int b) { return b==0 ?a:gcd (b,a%b); }
扩展欧几里得算法可以用于求方程 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) 的一组整数解 x , y x,y x , y 。
1 2 3 4 5 6 7 8 9 int exgcd (int a,int b,int &x,int &y) { if (!b){ x = 1 ,y = 0 ; return a; } int t = exgcd (b,a%b,y,x); y -= a / b * x; return t; }
二元一次方程 求特解根据翡蜀定理 ,类似于 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) 的方程必定有整数解。
推广到一般情况: a x + b y = c ax+by=c a x + b y = c 这样的普通二元一次方程方程也可以用exgcd
求解。
定义 t = g c d ( a , b ) t = gcd(a,b) t = g c d ( a , b ) ,如果 c ∣ t c|t c ∣ t 则有解,反之无解。
如果有解,定义 k = c t k = \frac{c}{t} k = t c ,将 c c c 除以 k k k 得一个新方程 a x + b y = t = g c d ( a , b ) ax+by=t=gcd(a,b) a x + b y = t = g c d ( a , b ) 。
这个新方程可以使用exgcd
解出一组特解 x 0 , y 0 x_0,y_0 x 0 , y 0 。因为新方程由原方程的 c c c 除以 k k k 得到,所以原方程的特解 { x 1 = x 0 × k y 1 = y 0 × k \begin{cases}x_1&=x_0 \times k\\ y_1&=y_0 \times k\end{cases} { x 1 y 1 = x 0 × k = y 0 × k
如果你想要的是x的最小正整数解 (使 x x x 最小),那么你可能需要对 x 1 , y 1 x_1,y_1 x 1 , y 1 做一些处理。
{ x 1 = ( x 1 m o d b + b ) m o d b y 1 = c − a x 1 b \begin{cases}x_1 &= (x_1 \bmod b + b) \bmod b \\y_1 &= \frac{c-ax_1}{b}\end{cases} { x 1 y 1 = ( x 1 m o d b + b ) m o d b = b c − a x 1
方便起见,后文的 x 1 , y 1 x_1,y_1 x 1 , y 1 都指这里的最小正整数解。
exgcd
找到的不一定是最小正整数解 (事实上,它甚至有可能不是正整数),但一定是整数解 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int exgcd (int a,int b,int &x,int &y) { if (!b){ x = 1 ,y = 0 ; return a; } int t = exgcd (b,a%b,y,x); y -= a / b * x; return t; }inline bool linear_equation (int a,int b,int c,int &x,int &y) { int t = exgcd (a,b,x,y); if (c%t!=0 ) return false ; int k = c / t; x *= k,y *= k; x = (x % b + b) % b; y = (c - ax) / b; return true ; }
求通解手玩一下方程 4 x + 2 y = 16 4x + 2y = 16 4 x + 2 y = 1 6 ,可以找到以下的正整数 解。
发现对于方程 a x + b y = c ax+by=c a x + b y = c ,把 x+=b/gcd(a,b),y-=a/gcd(a,b)
,便可以得到另一组解。
得到通解公式:
{ x = x 0 + m × b g c d ( a , b ) y = y 0 − m × a g c d ( a , b ) \begin{cases} x&=x_0+m \times \frac{b}{gcd(a,b)}\\ y&=y_0-m \times \frac{a}{gcd(a,b)} \end{cases} { x y = x 0 + m × g c d ( a , b ) b = y 0 − m × g c d ( a , b ) a
m m m 为任意整数。
很显然, x x x 越大 y y y 越小(因为 a x + b y ax+by a x + b y 的和恒定)。
这在求 x , y x,y x , y 的最大/最小值时非常有用。
正整数解的数量得出了通解公式后就可以得出正整数解的数量。显然,当 x x x 为最小正整数值时, y y y 为最大正整数值。
⌊ − x 1 + 1 b g c d ( a , b ) ⌋ ≤ m ≤ ⌊ y 1 − 1 a g c d ( a , b ) ⌋ \lfloor \frac{-x1+1}{\frac{b}{gcd(a,b)}} \rfloor \leq m \leq \lfloor \frac{y_1-1}{\frac{a}{gcd(a,b)}} \rfloor ⌊ g c d ( a , b ) b − x 1 + 1 ⌋ ≤ m ≤ ⌊ g c d ( a , b ) a y 1 − 1 ⌋
直接算出 m m m 的整数值数量即可。
只有正整数解 的数量,没有整数解 的数量。
二元不定方程整数解是无限多的。
线性同余方程类似于 a x ≡ b ( m o d m ) ax \equiv b \pmod m a x ≡ b ( m o d m ) 的方程被称为线性同余方程
。
原方程可以变换为 a x = m y + b ax = my + b a x = m y + b 即 a x − m y = b ax - my = b a x − m y = b 。
然后把 m m m 取相反数,就得到 a x + m y = b ax+my=b a x + m y = b 。
直接使用上一节提到的exgcd解二元一次方程
的方法就可以解出了。
别忘了把 y y y 取反!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int exgcd (int a,int b,int &x,int &y) { if (!b){ x = 1 ,y = 0 ; return a; } int t = exgcd (b,a%b,y,x); y -= a / b * x; return t; }int congruence_equation (int a,int b,int m) { int x,y,g=exgcd (a,m,x,y); if (b%g!=0 ) return -114514 ; return (x%m+m)%m; }
逆元众所周知,取模运算不影响加法,减法,乘法的结果,但是影响除法的结果。
所以如果题目需要你取模的式子中有除法,就需要使用逆元。
定义如果 a x ≡ 1 ( m o d m ) ax \equiv 1 \pmod m a x ≡ 1 ( m o d m ) ,则 x x x 称为 a m o d b a \bmod b a m o d b 的逆元,记作 a − 1 a^{-1} a − 1 。
求逆元求逆元的方法有exgcd
法,快速幂(费马小定理)法等。这里主要讲解exgcd
法。
求解逆元与求解线性同余方程是同一个原理。
1 2 3 4 5 6 7 8 9 10 11 12 13 int exgcd (int a,int b,int &x,int &y) { if (!b){ x = 1 ,y = 0 ; return a; } int t = exgcd (b,a%b,y,x); y -= a / b * x; return t; }int inv (int a,int m) { int res,qwq,g = exgcd (a,m,res,qwq); return res; }