gcd与扩gcd总结

gcd 定理的证明&＃xff1a;

模板&＃xff1a;

ll gcd(ll a,ll b)
{if(b &＃61;&＃61; 0) return a;else return gcd(b,a%b);
}

 

 扩gcd证明&＃xff1a;

模板&＃xff1a;

ll extgcd(ll a,ll b,ll &x,ll &y)
{ll d &＃61; a;if(b &＃61;&＃61; 0){x &＃61; 1;y &＃61; 0;} else{d &＃61; extgcd(b,a%b,y,x);y -&＃61; (a/b)*x;}return d;
}

 

解题规律&＃xff1a;

首先化为 ax&＃43;by &＃61; c 的形式&＃xff0c;一般采用增加常量的方式&＃xff0c;然后把a,b,x,y 代入extgcd 模板&＃xff0c;返回的是d &＃61; gcd(a,b)

得到的x 是 ax&＃43;by &＃61; gcd(a,b)&＃61;d 的一个解&＃xff0c;这时候两边同时乘以c/d就能得到解x’ &＃61; x * c/d