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{解}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据