Notice that on the left edge of column ~i~, the imaginary line is at height ~\frac{N}{M}\cdot (i-1)~, and on the right edge, it is at height ~\frac{N}{M}\cdot i~. Hence, it fully intersects all the pixels from rows ~\left\lfloor \frac{N}{M}\cdot (i-1) \right\rfloor + 1~ to ~\left\lceil \frac{N}{M}\cdot i \right\rceil~ in column ~i~. We can print all of these pixels in ~\mathcal{O}(1)~ per pixel, then repeat this process for all other columns to find every lit pixel. One can show that the total number of lit pixels cannot exceed ~N + M - 1~, so the overall time complexity is ~\mathcal{O}(N + M)~.

To avoid rounding errors, you may want to use integer division instead of the floating-point floor/ceiling functions.

Time complexity: ~\mathcal{O}(N + M)~