外贸网站建设哪家合适,石家庄规划,河北建设工程信息网下载时间,小程序商城开发北京Acwing-基础算法课笔记之数学知识#xff08;扩展欧几里得算法#xff09; 一、扩展欧几里得算法1、裴蜀定理2、过程模拟3、代码模板 二、线性同余方程1、定义2、模拟过程3、结论证明 一、扩展欧几里得算法
1、裴蜀定理
对于任意正整数 a a a#xff0c; b b b#xff0… Acwing-基础算法课笔记之数学知识扩展欧几里得算法 一、扩展欧几里得算法1、裴蜀定理2、过程模拟3、代码模板 二、线性同余方程1、定义2、模拟过程3、结论证明 一、扩展欧几里得算法
1、裴蜀定理
对于任意正整数 a a a b b b那么一定存在非零整数 x x x y y y使得 a x b y e x g c d ( a , b ) axbyexgcd(a,b) axbyexgcd(a,b)
2、过程模拟
例如求 g c d ( a , b ) gcd(a,b) gcd(a,b) ∙ \bullet ∙当 b 0 b0 b0 时则可以直接返回 a a a 的值即最大公约数推理如下
根据公式 a x b y e x g c d ( a , b ) axbyexgcd(a,b) axbyexgcd(a,b)得 a × x 0 × y a a\times x0\times ya a×x0×ya ⇔ a × x a \Lrarr a\times xa ⇔a×xa ⇔ x 1 \Lrarr x1 ⇔x1 ⇒ y 0 \Rarr y0 ⇒y0 ∙ \bullet ∙当 b ̸ 0 b\not 0 b0 时求得扩展欧几里得算法 e x g c d ( b , a % b , y , x ) exgcd(b,a\%b,y,x) exgcd(b,a%b,y,x)推理如下 b y ( a by(a by(a m o d mod mod b ) x e x g c d ( a , b ) b)xexgcd(a,b) b)xexgcd(a,b) ⇒ a \rArr a ⇒a m o d mod mod b a − ⌊ a b ⌋ b ba-⌊\frac{a}{b}⌋b ba−⌊ba⌋b ⇒ b y ( a − ⌊ a b ⌋ b ) x e x g c d ( a , b ) \rArr by(a-⌊\frac{a}{b}⌋b)xexgcd(a,b) ⇒by(a−⌊ba⌋b)xexgcd(a,b) ⇒ a x b ( y − ⌊ a b ⌋ x ) e x g c d ( a , b ) \rArr axb(y-⌊\frac{a}{b}⌋x)exgcd(a,b) ⇒axb(y−⌊ba⌋x)exgcd(a,b)
3、代码模板
// 求x, y使得ax by gcd(a, b)
int exgcd(int a, int b, int x, int y)
{if (!b){x 1; y 0;return a;}int d exgcd(b, a % b, y, x);y - (a/b) * x;return d;
}Acwing-扩展欧几里得算法
二、线性同余方程
1、定义
给定 n n n 组数据 a i a_i ai b i b_i bi m i m_i mi对于每组数求出一个 x i x_i xi使其满足 a i × x i ≡ b i ( m o d a_i\times x_i\equiv b_i(mod ai×xi≡bi(mod m i ) m_i) mi)。
2、模拟过程
设 a 2 a2 a2 b 3 b3 b3 m 6 m6 m6此时以上并不满足条件。
设 a 4 a4 a4 b 3 b3 b3 m 5 m5 m5要使 4 x % 5 3 4x\%53 4x%53所以 x − 3 x-3 x−3或 x 2 x2 x2
3、结论证明 a × x ≡ b ( m o d a\times x\equiv b(mod a×x≡b(mod m ) m) m) ⇔ \Lrarr ⇔ ∃ y ∈ Z \exist y\in Z ∃y∈Z使得 a x m y b axmyb axmyb ⇔ a x − m y b \Lrarr ax-myb ⇔ax−myb ⇔ y ′ − y \Lrarr y-y ⇔y′−y ⇔ a x m y ′ g c d ( a , m ) \Lrarr axmygcd(a,m) ⇔axmy′gcd(a,m)条件 g c d ( a , m ) ∣ b gcd(a,m)|b gcd(a,m)∣b
