不定方程问题

一次不定方程

一次不定方程的公式为ax+by=c
如果数目较小的话，我们可以用暴力破解的方式来解决。

public class 不定方程 {
    public static void main(String[] args){
        for(int x=0;x<100;x++)
            for(int y=0;y<100;y++){
                if(4*x-5*y==7)
                    System.out.println(x+","+y);
            }
    }
}

但是，数目较大的时候该怎么求解呢？
其实一次不定方程的公式：ax+by=c，可以转化为ax=c-by
步骤如下:

1. 先求出一个特殊解
2. 求通解， x = x0 +bt; y = y0 - at

public class 不定方程 {
    public static void main(String[] args) {
        int x0 = 0, y0 = 0;
        //求特解
        for (int y = 0; y < 100; y++) {
            if (((7 + 5 * y) % 4) == 0) {
//                System.out.println("y0 = " + y + " ,x0 = " + ((7 + 5 * y) / 4));
                x0 = ((7 + 5 * y) / 4);
                y0 = y;
                break;
            }
        }
        //求通解
        for (int t = -25; t < 25; t++) {
            if (4*(x0 - 5 * t) - 5*(y0 - 4 * t) == 7)
                System.out.println("x" + " = " + (x0 - 5 * t) + " ,y = " + (y0 - 4 * t));
        }
    }
}