40023113线段上格点的个数

试题描述

给定平面上的两个格点P1=（x1，y1）和P2=（x2，y2），线段P1P2上，除了P1和P2以外一共有多少个格点？

输入

一行包括四个数，分别为x1,x2,y1和y2，两两之间用一个空格分隔。

输出

输出一个数，表示题目描述的格点的个数。

输入示例

1 5 11 3

输出示例

其他说明

数据范围：-10^9<=x1,x2,y1,y2<=10^9,x1,x2,y1,y2均为正整数。

辗转相除法求最大公约数，用递归。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 int x1,x2,y1,y2;
 5 int gcd(int a,int b)
 6 {
 7     if(b==0) return a;
 8     else return gcd(b,a%b);
 9 }
10 int main()
11 {
12     scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
13     if(x1-x2==0 && y1-y2==0) printf("0");
14     else cout<<gcd(abs(x1-x2),abs(y1-y2))-1;
15     return 0;
16 }

40023113线段上格点的个数