/*
问题描述:
线段上的格点
给定平面上的两个格点 P1 = (x1, y1) ; P2 = (x2, y2) 线段P1 P2上，除P1 和 P2以外一共有几个格点
*/
/*
分析过程
在格点上画P1(0,5) P2(5,0) 连接起来发现 这条线上的经过的格子的格点都在P1 P2这条线段上
将其不称 P1 P2为斜边的直角三角形 发现因为每一个小的三角形 和大三角形都是相似
再画P1(0, 8) P2(3,4) 这条线段上没有格点 但是如果向下扩展成一个边之比为2的一个相似三角形 得到
P1(0, 8) P2'(6, 0) 那么发现 刚才的P2(3,4)就是这个新的线段上的一个格点
所以也就是说 当线段中的点构成的三角形 和大三角形相似 且成整数倍的时候 这个格点就在格点上
那么要计算多少个这样的三角形 --->>找出最小的相似三角形 设P1(x1, y1) P2(x2,y2)
最小的三角形 直角边长 |x1-x2| / gcd(|x1-x2|, |y1-y2|) , |y1-y2| / gcd(|x1-x2|, |y1-y2|)
显而易见 那么这样最小三角形的个数 就是gcd(|x1-x2|, |y1-y2|)
所以这道题就是求gcd(|x1-x2|, |y1-y2|)
*/
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <queue> 5 #include <algorithm> 6 #define READ() freopen("in.txt", "r", stdin); 7 #define MAXV 2007 8 #define MAXE 20007 9 #define INF 0x3f3f3f3f3f3f3f3f 10 using namespace std; 11 12 typedef pair<int,int> P; 13 14 //复杂度 < O(log max(a,b)) 15 int gcd(int x, int y)//辗转相除法 16 { 17 if (y == 0) return x; 18 else return gcd(y , x % y); 19 } 20 int main() 21 { 22 READ() 23 P p1, p2; 24 int x, y; 25 scanf("%d%d", &p1.first, &p1.second); 26 scanf("%d%d", &p2.first, &p2.second); 27 x = abs(p1.first - p2.first); 28 y = abs(p1.second - p2.second); 29 // if (x < y) 30 // swap(x, y);可以不用swap因为 一次gcd后 自动就变为x > y 31 int ans = gcd(x, y); 32 cout << ans - 1 << endl;//因为最后一个是自己线段上这个端点 33 return 0; 34 }