gcdex的算法笔记

2021-12-16 本文已影响0人 areece

其实最主要的是那个递推公式，从
$ax + by = gcd(a,b) \\ bx' + (a\%b)y'= gcd(b, a\%b) \\ ax + by = bx' + (a - a/b * b)y' = ay' + b(x' - a/b * y') \\ x = y' \\ y = x' - a/b * y'$
终结的条件就是求 $gcd(b, 0) = b$ ，然后一路上反推上去就得到最后的 $x,y$