拓展欧几里得算法

来学数学！

拓展欧几里得算法 (EXGCD)

求 $ax+by=\gcd(a,b)$ 的整数解。

例：求 $6x+15y=\gcd(6,15)=3$ 的整数解。
有一组整数解 $x=3,y=-1$ 。（解不唯一）

求一组可行解

设存在 $x_1,y_1,x_2,y_2$ ，满足

$\left\{ \begin{aligned} &ax_1+by_1=\gcd(a,b)\\ &bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\\ \end{aligned} \right.$

因为 $\gcd(a,b)=\gcd(b,a\bmod b)$ ，所以 $ax_1+by_1=bx_2+(a\bmod b)y_2$ 。
又因为 $a\bmod b=a-b\lfloor\frac{a}{b}\rfloor$ ，所以 $ax_1+by_1=bx_2+(a-b\lfloor\frac{a}{b}\rfloor)y_2$ 。
整理得 $ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$ 。
即 $x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$ 。
则我们可以用 $a'=b,b'=a\bmod b$ 的方程的解来反向推出系数为 $a,b$ 方程的解。
边界条件： $b=0$ 时, 解为 $x=1,y=0$ 。

由此，我们得到重要结论 1：

重要结论 1
若 $bx+(a\bmod b)y=\gcd(b,a\bmod b)$ 的一组整数解为 $x=x_0,y=y_0$ ，则 $ax+by=\gcd(a,b)$ 的一组整数解为 $x=y_0,y=x_0-y_0\lfloor\frac{a}{b}\rfloor$ 。

模板代码

由此，可以写出代码。

void exgcd(int a,int b,int& x,int& y){
    if(!b){x=1,y=0;return; } // 边界条件
    exgcd(b,a%b,x,y); // 此时已经有 (x,y) 是方程的 (b,a%b) 一组解
    swap(x,y); // x' = y, 先让 y' = x
    y -= (a/b)*x; //y' = x-y*floor(a/b) 即 y = y-x'*floor(a/b) 
}

使用引用来递归计算。x 和 y，在回溯时一层一层更新。注意时间复杂度和欧几里得算法相同，为 $O(\log n)$ 。

对其稍加改造还可以一并求出 $\gcd(a,b)$ ，并且可以减少掉这个 swap 操作。

int exgcd(int a,int b,int& x,int& y){
    if(!b){x=1,y=0;return a;}
    int g = exgcd(b,a%b,y,x); // 注意：我们递归的时候反转顺序，这样就不用 swap 了
    y -= (a/b)*x; //y1 = x2-y2*floor(a/b) = x2-x1*floor(a/b) 
    return g;
}

返回值即为 $\gcd(a,b)$ 。

求出所有解

我们已经求出一组解，接下来尝试求出所有整数解。

设两组整数解为 $x_1,y_1$ 和 $x_2,y_2$ ，则 $ax_1+by_1=ax_2+by_2$ 。
整理， $a(x_1-x_2)=b(y_2-y_1)$ 。
设 $\gcd(a,b)=g$ ，左右两边同时除 $g$ ， $a'(x_1-x_2)=b'(y_2-y_1)$ 。
注意到此时 $a',b'$ 互素，则 $x_1-x_2=kb' (k\in \Z)$ ，带回得 $y_1-y_2=-ka'$ 。

由此，我们得到重要结论 2：

重要结论 2
若 $ax+by=\gcd(a,b)$ 的一组整数解为 $x=x_0,y=y_0$ ，则其所有整数解为 $x=x_0+kb',y=y_0-ka'$ ，式中 $a'=a/\gcd(a,b),b'=b/\gcd(a,b),k\in \Z$ 。

注意到在证明过程中我们没有用到 $ax+by$ 等于什么，因此得到重要结论 2 一般形式：

重要结论 2 一般形式
若 $ax+by=c$ （ $c$ 为任意整数）的一组整数解为 $x=x_0,y=y_0$ ，则其所有整数解为 $x=x_0+kb',y=y_0-ka'$ ，式中 $a'=a/\gcd(a,b),b'=b/\gcd(a,b),k\in \Z$ 。

求解线性丢番图方程

求方程 $ax+by=c$ 的所有整数解。

事实上 $c$ 不是 $\gcd(a,b)$ 的倍数时，此方程没有整数解。
下证：设 $\gcd(a,b)=g$ ，方程两边同除 $g$ ，得 $a'x+b'y=c/g$ 。此时等号左边时整数，故当且仅当 $c$ 为 $g$ 倍数时有解。（若 $ab=0$ ，可以特殊判断）

在其他情况可以用上面的进行推导，得到重要结论 3：

重要结论 3
对于方程 $ax+by=c$ ，当且仅当 $c$ 为 $\gcd(a,b)$ 倍数时有无数组整数解。
且若 $ax+by=gcd(a,b)$ 的一组解为 $x=x_0,y=y_0$ ，则此方程的一组解为 $x=x_0\frac{c}{\gcd(a,b)},y=y_0\frac{c}{\gcd(a,b)}$ 。

要求出这个方程的所有解用重要结论 2 一般形式即可。

例题

直线上的点：对于直线 $l:ax+by+c=0$ ，求有多少个整点 $(x,y)$ 满足 $x\in[x_1,x_2],y\in[y_1,y_2]$ ？保证给定直线不与坐标轴垂直。

例： $l:2x+3y+5=0$ ， $x_1=y_1=-5,x_2=y_2=5$ ，共有 $4$ 个满足要求的点，分别为 $(2,-3)$ ， $(5,-5)$ ， $(-1,-1)$ ， $(-4,1)$ 。

首先当 $c$ 不为 $\gcd(a,b)$ 倍数时，直线不经过任何整点，直接输出 0。

否则就可以求出 $ax+by=\gcd(a,b)$ 的一组整数解 $(x,y)$ 。则一个整点的坐标可以表示为 $(x+\frac{-c}{\gcd(a,b)},y\frac{-c}{\gcd(a,b)})$ 记作 $(x_0,y_0)$ 。

则有
$x_1\le x_0+kb' \le x_2$
$y_1\le y_0-ka' \le y_2$

求解不等式即可。

#include<bits/stdc++.h>
using namespace std;

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

int main(){
    int a,b,c;
    int x1,x2,y1,y2;
    scanf("%d%d%d",&a,&b,&c);
    scanf("%d%d%d%d",&x1,&x2,&y1,&y2);

    int x,y;
    int g = exgcd(a,b,x,y);

    if(c%g !=0){
        puts("0");return 0;
    }
    int x0 = x*-c/g, y0=y*-c/g; 
    int ap = a/g,bp=b/g;

    
    double l1 = (x1-x0)*1.0/bp;
    double r1 = (x2-x0)*1.0/bp;
    if(l1>r1)swap(l1,r1); // k 前面系数正负 影响不等式方向

    double l2 = -(y1-y0)*1.0/ap;
    double r2 = -(y2-y0)*1.0/ap;
    if(l2>r2)swap(l2,r2);

    int l = max(ceil(l1),ceil(l2));
    int r = min(floor(r1),floor(r2));

    if(l>r)puts("0");
    else printf("%d\n",r-l+1);

    return 0;
}