Problem Link: http://lightoj.com/volume_showproblem.php?problem=1077

For pdf Click here

As the problem says to find the lattice points from (Ax, Ay) to (Bx, By).My idea was to find the number of solutions of the equation x * (Ay-By) — y * (Ax-Bx) = Ax * ( Ay-By) — Ay * (Ax-Bx) which is basically Extended Euclid. I got WA so many times. And after that I found this. But I can't understand why this problem can't be solved using Extended Euclid. Can anybody Please explain ? After solving this problem I thought either I don't understand Extended Euclid or there is a bug in my code.