# GNAQ 的模板重建计划 – 数学推导部分

exgcd 部分

$$\mathrm{exgcd} \text{的构造方法}$$ $$\text{考虑} ax+by=\mathrm{gcd}\left( a,b \right)$$ $$bx_1+\left( a-\lfloor \frac{a}{b} \rfloor b \right) y_1=\mathrm{gcd}\left( b,a\,\,\mathrm{mod} b \right)$$ $$\text{移项构造}, \text{分离} a, b$$ $$ay_1+b\left( x_1-\lfloor \frac{a}{b} \rfloor y_1 \right) =\mathrm{gcd}\left( a,b \right)$$ $$x=y_1, y=x_1-\lfloor \frac{a}{b} \rfloor y_1$$ $$\blacklozenge$$ $$\mathrm{exgcd} \text{的一般推广}$$ $$ax+by=c$$ $$c\nmid \mathrm{gcd}\left( a,b \right) \Rightarrow \text{无整解}$$ $$c\mid \mathrm{gcd}\left( a,b \right) \Rightarrow \left\{ x_1=x_0\cdot \frac{c}{\mathrm{gcd}\left( a,b \right)}, y_1=y_0\cdot \frac{c}{\mathrm{gcd}\left( a,b \right)} \right\}$$ $$\text{考虑} x, y\,\,\text{的正负限制和解的变换}$$ $$\text{变换方程为} a\left( x_1+db \right) +b\left( y_1-da \right) =c$$ $$\text{其中} d\,\,\text{是} \left\{ db,da \right\} \subseteq \mathbb{Z}\,\,\text{的数}$$ $$\text{思考得} \frac{1}{\mathrm{gcd}\left( a,b \right)}\,\,\text{为} d\,\,\text{最小的可能正取值}$$ $$a\left( x_1+k\frac{b}{\mathrm{gcd}\left( a,b \right)} \right) +b\left( y_1-k\frac{a}{\mathrm{gcd}\left( a,b \right)} \right) =c, k\in \mathbb{Z}$$ $$\text{如果}\begin{cases} x>0 \\ y>0 \end{cases}\,\,\text{则有}\begin{cases} x_1+k\frac{b}{\mathrm{gcd}\left( a,b \right)}>0 \\ y_1-k\frac{a}{\mathrm{gcd}\left( a,b \right)}>0 \end{cases}$$ $$\text{解得} l\xlongequal{\mathrm{def}}\lceil \frac{-x_1+1}{\frac{b}{\mathrm{gcd}\left( a,b \right)}} \rceil \leqslant k\leqslant \lfloor \frac{y_1-1}{\frac{a}{\mathrm{gcd}\left( a,b \right)}} \rfloor \xlongequal{\mathrm{def}}r$$ $$\text{若} k=l, \text{则此时} x\,\,\text{取到正最小值}, y\,\,\text{取到正最大值}$$ $$k=r\,\,\text{同理}.$$ $$\text{若} r>l\,\,\text{则无} x,y>0 \text{解}$$