18图灵班作业5-编程

给定平面上两个格点P1和P2，求线段P1P2上除了P1和P2之外还有多少个格点。注：格点就是平面中横竖坐标值都为整数的点。直白说，就是给定两个格点，把它们连线，求连线上的其他格点的个数。

$$设p_1(x_1,y_1),p_2(x_2,y_2),则ans=gcd(abs(x_1-x_2),abs(y_1-y_2))-1\\ 证明如下\\平移坐标系，使p_{1^"}(0,0),p_{2^"}(x_2-x_1,y_2-y_1). 不妨设lp_1p_2的斜率为k，且满足\\ k=\frac{a}{b},gcd(a,b)=1\\ 也就是说假设从原点出发开始递进，要使接下来的每个点都在坐标系上，且在线段lp_1p_2上则要有\\ x=ca,y=cb且c\in\mathbb{N_+},0<x<x_{2}-x_{1},0<y<y_{2}-y_{1}\\ 即满足条件的c有多少个，就有多少个解。\\ 当满足x=x_2-x_1,y=y_2-y_1,即ca=x_2-x_1,cb=y_2-y_1时\\ 因为gcd(a,b)=1，可得c=gcd(abs(x_1-x_2),abs(y_1-y_2))\\ 即有0<c<gcd(abs(x_1-x_2),abs(y_1-y_2)),也即满足条件的c有gcd(abs(x_1-x_2),abs(y_1-y_2))-1个$$

代码实现如下：

#include <cstdio>
#include <cmath>
int binary_gcd(int a,int b){
    if(a==b) return a;
    if(a==0) return b;
    if(b==0) return a;
    if((~a&1)&&(~b&1)) return (binary_gcd(a>>1,b>>1))<<1;
    if((~a&1)&&(b&1)) return binary_gcd(a>>1,b);
    if((~b&1)&&(a&1)) return binary_gcd(a,b>>1);
    if(a>b) return binary_gcd((a-b)>>1,b);
    else return binary_gcd((b-a)>>1,a);
}
int main(){
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    printf("%d",binary_gcd(abs(x1-x2),abs(y1-y2))-1);
    return 0;
}