Solution of Light OJ - 1077 - How Many Points?

 Problem Statement :
         Given two points A and B on the X-Y plane, output the number of the lattice points on the segment AB. Note that A and B are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both x and y co-ordinate as integer.

For example, for A (3, 3) and B (-1, -1) the output is 5. The points are: (-1, -1), (0, 0), (1, 1), (2, 2) and (3, 3).

Problem Solution :

     Let one of the points be 

⟨a,b⟩ and the other ⟨c,d⟩; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining ⟨0,0⟩ to ⟨c−a,d−b⟩. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to ⟨m,n⟩ for integers m and n. Look at the equation of the line containing this segment: it’s

y=nmx.

Suppose that when you reduce nm to lowest terms, you get ab. Then your equation is

y=abx,

and y is an integer if and only if b∣x.

Suppose that the points are ⟨−2,55⟩ and ⟨1011,1055⟩. I’d look at the segment from the origin to ⟨1011−(−2),1055−55⟩=⟨1013,1000⟩. It lies on the line

y=10001013x.

Any lattice point on that line must have both x and y integers, so suppose that x is an integer. When is 10001013x an integer? The fraction is in lowest terms, so this occurs only when x is a multiple of 1013. On the other hand, we’re looking only at the segment between ⟨0,0 and ⟨1013,1000⟩, so clearly we must have 0≤x≤1013. How many multiples of 1013 are there in this range? Just two, 0 and 1013. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding ⟨2,−55⟩ to restore the original endpoints doesn’t change the number of lattice points, so ⟨−2,55⟩ and ⟨1011,1055⟩ are the only lattice points on the original segment.

Solution Code  :

        #include <stdio.h>

long long Ax, Ay, Bx, By, dx, dy;
long long ABS (long long n)
 {
       return n> 0? n:-n;
 }

long Gcd(long long a,long long b)
{
    if(b==0)
        return a;
    else
        return Gcd(b, a%b);
}

int main()
{
      int i, T;
      scanf ("%d",&T);
      for (i = 1; i <= T; i++)
      {
                scanf ("%lld %lld %lld %lld",&Ax,&Ay,&Bx,&By);
                printf ("Case %d: %lld\n", i, Gcd(ABS(Ax-Bx),ABS(Ay-By))+1);
      }
      return 0;
}