Uva-11768 Lattice Point or Not题解

知识：扩展gcd
题目：题目链接

Now a days a very common problem is:“The coordinate of two points in Cartesian coordinate system is (200, 300) and (4000, 5000).If these two points are connected we get a line segment. How many lattice points are there on this line segment”.You will have to do a similar task in this problem — the only difference is that the terminal coordinates can be fractions.
Input
First line of the input file contains a positive integer N (N ≤ 50000) that denotes how many lines of inputs follow. This line is followed by N lines each of which contains four floating-point numbers x1,y1, x2, y2 (0 < |x1|, |y1|, |x2|, |y2| ≤ 200000). These floating-point numbers has exactly one digit after the decimal point.
Output
For each line of input except the first line produce one line of output. This line contains an integer which denotes how many lattice points are there on the line segment that connects the two points (x1, y1) and (x2, y2).
Sample Input
3
10.1 10.1 11.2 11.2
10.2 100.3 300.3 11.1
1.0 1.0 2.0 2.0
Sample Output
1
0
2

题意：给你两个带一位小数的点坐标，问你在这两个点的连线上有多少个整数点坐标。
思路：利用扩展gcd，求得参数方程通解，在范围内计数 t 。（PS：看完思路后尽量自己先去做一下，实在想不到再看具体方法解析）
方法：

1. 首先都是一位小数，先将坐标扩大十倍
2. 然后根据题意有一般方程，即（y1-y2）X+（x2-x1）Y=x2*y1-x1*y2
3. 再利用扩展gcd求得一组x0,y0，ax0+by0=gcd（a,b）;由通解方程知 x’=x0*（c/d）；b’=b/d；（ax’+by’=c；b’ = b/gcd(a,b)；d=gcd(a,b)）
4. 最后利用 floor((x2-x)/b’) - ceil((x1-x)/b’) + 1 (x2 >= x1, )

PS:通解方程： y = y’ - a’t 、 x = x’ + b’t {a’ = a/gcd(a,b) b’ = b/gcd(a,b)}
//需注意x1==x2或y1==y2时需特判
代码实现：

#include<bits/stdc++.h> // Uva-11768 Lattice Point or Not
#define LL long long  
using namespace std; 
int n;   

LL ex_gcd(LL a,LL b,LL &x,LL &y)//扩展gcd
{
    LL d = a;
    if(!b) x = 1,y = 0;
    else{
      d = ex_gcd(b,a%b,y,x);
      y-=a/b*x;
    }
    return d;
} 

LL solve(double x1,double y1,double x2,double y2)
{
    LL ix1=x1*10 , iy1=y1*10 , ix2=x2*10 , iy2=y2*10;
    if(ix1==ix2){
        if(ix1%10==0) 
            return floor(max(y1,y2))-ceil(min(y1,y2))+1; 
        else return 0;
    }
    if(iy1==iy2){
        if(iy1%10==0) 
            return floor(max(x1,x2))-ceil(min(x1,x2))+1; 
        else return 0;
    }
    //点斜式 推得 下式 a,b,c 
    LL a=(iy1-iy2)*10 , b=(ix2-ix1)*10 , c=ix2*iy1 - ix1*iy2;//这再乘一次十是因为 c （c相当于乘100) 
    LL x,y, d=ex_gcd(a,b,x,y);
    if(c%d) return 0;// c不能整除gcd(a,b) 表明没有整数解 
    b/=d; x*=(c/d); 
    if(x1>x2) swap(x2,x1);
    return floor((x2-x)/b) - ceil((x1-x)/b) +1 ;  //关键 
}
int main()  
{  
    cin>>n;
    while(n--){
        double x1,y1,x2,y2;
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        printf("%lld\n",solve(x1,y1,x2,y2));    
    }
    return 0;  
}