扩展欧几里得算法

这一篇文章的主角就是大名鼎鼎的数学家欧几里得。很多刚了解一些数论的ACMer都会接触到辗转相除法，其实这就叫做欧几里得算法，但是这并不会是我们今天所讲的内容，我们今天讲的算法叫做扩展欧几里得。

扩展欧几里得

这个算法主要就是求一个式子的解：ax+by=gcd(a,b)
首先我们可以知道当b=0时，即有x=1,y=0，当b>0的时候我们可以进行推导，因为gcd(a,b)=gcd(b,a mod b),我们可以带入式子推出bx‘+(a mod b)y’=gcd(b,a mod b)=gcd(a,b),我们可以回代得到下面的式子
bx’+(a-a/b*b)y’=gcd(a,b)
ay’+bx’-(a/b)*by’=gcd(a,b)
ay’+b(x’-a/b*y’)=gcd(a,b)
最后我们可以和最初的式子ax+by=gcd(a,b)一起得出x=y’,y=x’-a/b*y’
这样我们就可以求出这个式子的解了

直线上的点

求直线上ax+by+c=0有多少个整数点（x,y），使得其满足x属于[x1,x2],y属于[y1,y2]。

我们可以先利用扩展欧几里得求出一组解，然后通过这一组解就可以得到所有的解了

代码

#include <iostream>
using namespace std;

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

int main(){
    cout << "请依次输入a,b,c,x1,x2,y1,y2：";
    int a,b,c,x,y,x1,x2,y1,y2;
    cin>>a>>b>>c>>x1>>x2>>y1>>y2;
    int g=extend_gcd(a,b,x,y);
    if(c%g==0){
        int x0 = -x*(c / g), y0 = -y*(c / g);//ax+by=-c
        cout << '(' << x0 << ',' << y0 << ')' << endl;
        bool kup = true, kdown = true;
        for (int k = 1 ;; k++){
            int xn = x0 - k*(b/g), yn = y0 + k*(a/g);
            if (kup&&xn >= x1&&xn <= x2&&yn >= y1&&yn <= y2)
                cout << '(' << xn << ',' << yn << ')' << endl;
            else kup = false;
            xn = x0 + k*(b / g);
            yn = y0 - k*(a / g);
            if (kdown&&xn >= x1&&xn <= x2&&yn >= y1&&yn <= y2)
                cout << '(' << xn << ',' << yn << ')' << endl;
            else kdown = false;
            if (!(kup || kdown)) break;
        }
    }else
        cout << "No Point." << endl;
    return 0;
}