Cannot understand the Editorial

I am unable to understand the ICPC problem’s solution Problem.
I do not understand that how this came up (how this striked? and how does it leads us to number of integral points!)

Dx = (x2 - x1)
Dy = (y2 - y1)

x = x1 + Dx * t
y = y1 + Dy * t

Please help me!! Why have we written it like this , it is quite non striking for me ! Morover,the next statements are unclear. I just need to know how to calculate the number of Integral points through which the line segment passes.

ok, Let me try, we need number of integral points between x1,y1 and x2,y2 … they can be anything like
a1,b1, a2,b2,… say till q-1 and qth integral point is x2,y2 ok?

first thing to be noticed! a1,b1 are integers right? so basically a1 is x1 + something11,a2 is x1+ something12 … and aq = x2 = x1 + something1q … same is case for y, b1 is y1 + something21,b2 is y1+ something22 … and bq = y2 = y1 + something2q …! so we are dividing x2-x1 into q parts and y2-y1 into q parts

we get this result that, q is factor of x2-x1 and y2-y1 and so we get q = gcd(x2-x1,y2-y1), say Dx = (x2-x1) and Dy = (y2-y1) so any point x = x1 + Dxt and y = y1 + Dyt where t is p/q ( q is gcd and p is 1,2,3,4…q )
Hope so i was clear

1 Like

Q is a factor x2-x1 and y2-y1 does not imply it is the GCD

yes Q is a factor of x2-x1 and y2-y1 and gcd is a factor, we have to find number of integral point, as t is p/q where p = (1,2,3,4…q) we need to maximize q, which will be when it is a gcd.

Lets say the points are (x1,y1) and (x2,y2). Shift the points so that (x1,y1) lies at origin.
New points: (0,0) and (x2-x1,y2-y1)
Line joining these two points of form y=mx+c, where m = (y2-y1)/(x2-x1) and c=0
say x is integer, for y to be integer: ((y2-y1)x)%(x2-x1) == 0
take abs(y2-y1) = a, and abs(x2-x1) = b. So now required condition is (a
x)b == 0. Let g = gcd(a,b). Let a1=a/g and b1=b/g. now the relation becomes (a1*x*g)(b1g) == 0 where a1 & b1 are co-prime.
Problem can now be stated as number of x such that (a1
x)%b1 == 0 where a1,b1 and x are defined above.
Lets say range of x is [0,R] where R = abs(x2-x1), 0 and R inclusive
Number of x would be multiples of b1 in range of x. This is because a1 and b1 have no common factors other than 1, so for the modulo to become 0 there should be a multiple of b1 in numerator.
So number of multiples would be floor(R/b1) + 1.(Extra 1 is for 0).Now subtract the two end points and ans becomes floor(R/b1) - 1. Substitute the values and it becomes floor(abs(x2-x1)/(b/g)) - 1 and b is abs(x2-x1).
After cancelling from numerator and denominator ans is floor(g) - 1 or g-1. Putting value of g ans becomes gcd(y2-y1,x2-x1) - 1.

//