# Painting cells on the diagonals of a grid rectangle

In a grid rectangle 20210 × 1505, two diagonals are drawn, and all the cells containing segments of diagonals are painted. How many cells are painted?

• Do you count cells or lines? I.e. 20210 x 1505 cells meaning 20211 horizontal lines and 1506 vertical lines or 20210 x 1505 grid intersection points meaning 20209 x 1504 cells? Apr 4, 2021 at 7:42

in a $$94\times7$$ rectangle (1/46225th of the original one, since GCD of 20210 and 1505 is 215), a single diagonal will paint the following cells: a segment in row 1 (lowermost), then another segment in row 2, etc. up to row 7. The segments form a "ladder" (since the diagonal continuously rises when running left-to-right) and always overlap by 1 cell (since 94 and 7 are coprime, the diagonal does not run through the lattice points). The total length of the 7 segments is 94 (the entire width of the rectangle) plus 6 overlappings of 1 cell each, totaling to 100 (precisely, the columns 14, 27, 41, 54, 68 and 81 will be painted twice - the numbers are $$\mathrm{ceil}\left(\frac{94k}{7}\right), k=1,2,\dots,6$$).
In a large $$20210\times1505$$ rectangle, each of the diagonals runs through 215 such smaller $$94\times7$$ rectangles (if we divide the large rectangle into 46225 small ones). So, the two diagonals cover $$2\times215\times100=43000$$ squares, but 14 of them is covered by both (since $$1505$$ is an odd number, the diagonals intersect on the edge of a cell, not on a lattice point). So, we must subtract 14, and 42986 is the final answer.