新建网站怎么做,网站 建设理由,手机网站外链怎么,江西网站开发方案扩展欧几里得算法
求 a x b y d axbyd axbyd 的一组解#xff0c; d gcd ( a , b ) d \gcd(a,b) dgcd(a,b)。
辗转相除递归求解。
假设已经求出 b x ( b m o d a ) y d bx (b \bmod a)y d bx(bmoda)yd 的一组解。 a x b y b x ′ ( b m o d a ) y ′ b x …扩展欧几里得算法
求 a x b y d axbyd axbyd 的一组解 d gcd ( a , b ) d \gcd(a,b) dgcd(a,b)。
辗转相除递归求解。
假设已经求出 b x ( b m o d a ) y d bx (b \bmod a)y d bx(bmoda)yd 的一组解。 a x b y b x ′ ( b m o d a ) y ′ b x ′ ( b − b × ⌊ a b ⌋ ) y ′ a y ′ b ( x ′ − ⌊ a b ⌋ y ′ ) axbybx(b\bmod a)y\\ bx(b-b \times \lfloor\frac{a}{b} \rfloor)y\\ ayb(x- \lfloor\frac{a}{b}\rfloor y) axbybx′(bmoda)y′bx′(b−b×⌊ba⌋)y′ay′b(x′−⌊ba⌋y′)
则 x y ′ , y x ′ − ⌊ a b ⌋ y ′ x y, y x - \lfloor\frac{a}{b} \rfloor y xy′,yx′−⌊ba⌋y′。递归计算即可。 b 0 b 0 b0 时由辗转相除得 a d a d ad则 x 1 , y 0 x1,y0 x1,y0 显然是一组解。
void exgcd(int a, int b, int x, int y)
{if(b 0) return x 1, y 0, void();exgcd(b, b%a, y, x), y - (a / b) * x;
}扩欧求逆元
求 a a a 在模 p p p 下得逆元等价于求 a x ≡ 1 ( m o d p ) ax \equiv 1 \pmod p ax≡1(modp)等价于 a x p y ≡ 1 ( m o d p ) ax py \equiv 1 \pmod p axpy≡1(modp)。 gcd ( a , p ) 1 \gcd(a,p)1 gcd(a,p)1 时才有解即 a a a 有逆元。
裴属定理
我们对问题加以扩展求解 a x b y c ax by c axbyc。
裴属定理方程有解当且仅当 gcd ( a , b ) ∣ c \gcd(a,b) \mid c gcd(a,b)∣c。
若方程有解则用扩欧求出 a x b y d ax by d axbyd 对一组特解后乘以 c d \frac c d dc 即可由裴属定理得 c d \frac c d dc 为整数。
再找出特解后加上 a x b y 0 axby0 axby0 的解即可得到该不定方程的通解。
