一个神奇的思路(已过)
查看原帖
一个神奇的思路(已过)
816777
gengziyang2010楼主2025/6/16 15:28

当判断方程有没有正整数解的情况时,我们可以先用裴蜀定理算出特解,然后算出xminx_{min}yminy_{min}(均大于0):

xmin=(xmodbd+bd)modbdx_{min}=(xmod\frac{b}{d}+\frac{b}{d})mod \frac{b}{d}

ymin=(ymodad+ad)modady_{min}=(ymod\frac{a}{d}+\frac{a}{d})mod \frac{a}{d}

那么此时,如果方程没有正整数解,我们令x=xminx=x_{min},则对应的yy应为负数,再令y=yminy=y_{min},那么有

ax+by>cax+by>c

一定成立,据此可以判断方程有没有正整数解。

2025/6/16 15:28
加载中...