by "L. Shyamal" <lshyamal@[EMAIL PROTECTED]
>
Mar 9, 2007 at 07:59 PM
> >I have a square grid of unit size. If i have a line between any two
> > points, how do i find out the number of the intersecting squares.
>
> > -
> > Anush
Many years ago a local Math olympiad had this question. If you look at
a grid of m rows and n columns and have a diagonal through it, this
diagonal goes through (
gcd(m,n)* ((m+n)/gcd(m,n) - 1)
where gcd is the greatest common denominator function.
hth
best wishes
Shyamal
