LightOJ 1077 How Many Points?

Description

Given two pointsAandBon theX-Yplane, output the number of the lattice points on the segmentAB. Note thatAandBare also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have bothxandyco-ordinate as integer.

For example, forA (3, 3)andB (-1, -1)the output is5. The points are:(-1, -1), (0, 0), (1, 1), (2, 2) and (3, 3).

Input

Input starts with an integerT (≤ 125), denoting the number of test cases.

Each case contains four integers,A_x, A_y, B_xandB_y. Each of them will be fit into a32bit signed integer.

Output

For each test case, print the case number and the number of lattice points betweenAB.

Sample Input

2

3 3 -1 -1

0 0 5 2

Sample Output

Case 1: 5

Case 2: 2

题目很简单,就是让你求两个整数点连成的线段上的整数点（包括两端）有多少个

比如（1，1）（3，3）之间的点有（1，1），（2，2），（3，3）三个点；

看到这个题我想用斜率来做，结果做了两个小时还是不对，后来才知道思路不对，求下公约数就能出来；

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
    int tCase,t=1;
    long long x1,y1,y2,x2;
    scanf("%d",&tCase);
    while(tCase--)
    {
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        printf("Case %d: %lld\n",t++,(long long)__gcd(abs(y2-y1),abs(x2-x1))+1);
    }
    return 0;
}