前言： \(\operatorname{exgcd}\)，顾名思义，是\(\gcd\)的一种扩展。\(\gcd\)是求最大公因数，所用到的是辗转相除法，基于\(\gcd(a,b)=\gcd(b,a\modb)(a>b)\)的原理，在学习\(\operatorname{exgcd}\)前，请确保已掌握\(\gcd\),并懂得一点数学归纳法。如果您已掌握这些前置知识，请开始学习。 例题： 先看这样一道题，给定整数\(a,b\)，求\(x,y\)使得\(ax+by=1\)。 性质： 性质1： 这显然是一道数学题（废话），考虑将原式根据乘法分配律转换为\(\gcd(a,b)\times(\fra...