二元线性丢番图方程

方程形如ax + by = c(a,b,c已知整数,x,y为变量,求整数解)

几何意义上,只要这条直线上有整数坐标点就有无数解

定理:

记gcd(a,b)为d. 如果d%c != 0 无解,不然有无数解

记一个特解为x0,y0,则通解为(n为任意整数)

如25x + 15y = 70

一个特解为x0 = 4, y0 = -2

通解为x = 4 +3n, y = -2 - 5n

求特解(拓展gcd)

ax + by = gcd(a,b),如果用拓展gcd可以求出gcd(a,b)的同时求出x和y

就是在gcd的过程中记录一下x和y,大概的推导过程

得

(这里a/b是取整的哦)

化简得到

我们得出了前后式的关系,gcd最深层的时候a是1,b是0,我们可以倒序逆推得到xy

1
2
3
4
5
6
7
8
9
10
11
12

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); 
    y -= (a / b) * x;
    return d;
}

了解了拓展gcd之后,回到二元线性丢番图

现求ax + by = c

一:判断gcd(a,b) % c

二:用拓展gcd求特解x0,y0

三:

两边同乘

得到

四:

ax + by = c与三对照得出特解

五:

通解得出

如果要求最小正整数解的话,如果有y = x + a*t， 那么y的最小正整数y’可以这么求：

y’ = (x % t + t) % t;原因是因为t可能为负数,+t取正