对于不定方程\(ax+by=c\)有正数解的充分必要条件是\(c|gcd(a,b)\)，证明请看裴蜀定理
那么显然的，我们只要能解出方程\(ax+by=gcd(a,b)\)然后把解\(\times \frac{c}{gcd(a,b)}\)即可
如何解这个新的方程呢？我们知道\(gcd(a,b)\)，并且它等于\(gcd(b,a%b)\),也就是说，方程
\(bx+(a%b)y=gcd(b,a%b)\)和它同解，那么我们就对问题进行了转化，并且可以发现到最后方程将变为
对于不定方程\(ax+by=c\)有正数解的充分必要条件是\(c|gcd(a,b)\)，证明请看裴蜀定理
那么显然的，我们只要能解出方程\(ax+by=gcd(a,b)\)然后把解\(\times \frac{c}{gcd(a,b)}\)即可
如何解这个新的方程呢？我们知道\(gcd(a,b)\)，并且它等于\(gcd(b,a%b)\),也就是说，方程
\(bx+(a%b)y=gcd(b,a%b)\)和它同解，那么我们就对问题进行了转化，并且可以发现到最后方程将变为