*(number of integeral points on a linear line )

Problem Statement    Problem Statement for DreamingAboutCarrots Problem Statement      John works at a company called "FIELD-Tech", and today, he was so tired after work that he fell asleep as soon as he got home. Unfortunately, even in his sleep, he was unable to forget about his work. In one dream, he was asked to help a carrot producing company deal with the following question: how many carrots grow on a line segment connecting two given carrots? The endpoints of the segment (i.e., the two given carrots) should not be included. It's a rather strange question, and to make it even stranger, the company's representatives (guys who have carrots instead of heads) said that all the carrots grow on an infinite plane, and there is exactly one carrot at each point with integer coordinates. You must help tired John deal with this problem. The coordinates of the two carrots are (x1, y1) and (x2, y2). Return the number of carrots that lie strictly on the line segment connecting these carrots.   Definition      Class: DreamingAboutCarrots Method: carrotsBetweenCarrots Parameters: int, int, int, int Returns: int Method signature: int carrotsBetweenCarrots(int x1, int y1, int x2, int y2) (be sure your method is public)        Constraints - x1, y1, x2, and y2 will each be between 0 and 50, inclusive. - (x1, y1) and (x2, y2) will represent different points.   Examples 0)      1 1 5 5 Returns: 3 There are three points inside of the segment: (2,2), (3,3) and (4,4). 1)      0 0 1 1 Returns: 0 2)      50 48 0 0 Returns: 1 3)      0 0 42 36 Returns: 5 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:         Single Round Match 401 Round 1 - Division II, Level One

-------------------------------------------editorial------------------------------------------------------------------

2down vote

It is simply GCD(x1−x2,y2−y1)$GCD(x_1-x_2,y_2-y_1)$ . I can explain if anyone wants to, just because this post is so old , I dont think anyone will bother to see it EDIT: Let the equation of line be : y−y1x−x1$\frac{y-y1}{x-x1}$ = y2−y1x2−x1$\frac{y2-y1}{x2-x1}$ Now just switching the positions of these expressions we get: y−y1y2−y1$\frac{y-y1}{y2-y1}$ = x−x1x2−x1$\frac{x-x1}{x2-x1}$ Now , y - y1 should be equal to k * y2−y1GCD(y2−y1,x2−x1)$\frac{y2-y1}{GCD(y2-y1,x2-x1)}$ . Why ? x should be integer! if we write x in terms of everything else We will see y−y1y2−y1$\frac{y-y1}{y2-y1}$ should be Integer. Now I say that k1=0 Gives me y1 , to find the final kn , I put y= y2 into this equation (x2,y2 is the last integral point) . That gives me kn=GCD(y2−y1,x2−x1)$GCD(y2-y1,x2-x1)$ . Now , every k between 0 and this kn are integral points! If you include the initial point too ans is GCD(y2−y1,x2−x1)$GCD(y2-y1,x2-x1)$ +1 . If you exclude initial and final points ans is GCD(y2−y1,x2−x1)$GCD(y2-y1,x2-x1)$ -1.