Tham khảo:
Another alternative explanation.
Mark the leftmost square crossed of each row as ‘r’, and the topmost crossed square of each column with ‘c’. Thus, each square can be marked either ‘r’ or ‘c’ or ‘both r and c’ or ‘neither r nor c’. We’ll examine each case.
For a square to be marked both ‘r’ and ‘c’, the diagonal must pass through the upper left corner of the square.
For square to be marked ‘r’, diagonal should pass through its upper edge.
For square to be marked ‘c’, diagonal must pass through its left edge.
For square to be marked neither ‘r’ nor ‘c’, diagonal must pass through it’s upper as well as left edge, which is not possible. Therefore, no triangles are unmarked.
Now, no. of squares crossed = no. of squares marked ‘r’ + no. of squares marked ‘c’ - no. of squares marked both ‘r’ and ‘c’
Now, no. of r’s = no. of rows (only 1 leftmost crossed square in each row)
no. of c’s = no. of columns (only 1 topmost crossed square in each column)
all rows and columns are crossed by the diagonal.
Therefore, squares crossed = rows + columns - (no. of squares marked both ‘r’ and ‘c’)
Now, only 1 square is marked both ‘r’ and ‘c’ as 199 and 991 are coprime.
Therefore squares crossed = 199 + 991 - 1 = 1189
For a rectangle of size m×nm×n with sizes being coprime:
when a diagonal leaves the starting corner, it goes through the first square;and before it reaches the opposite corner it crosses n−1n−1, say, horizontal lines of the grid, and m−1m−1 vertical lines, each time entering a new square.So the diagonal visits m+n−1m+n−1 unit squares.
For sizes not coprime let d=gcd(m,n)d=gcd(m,n). Then we can reduce the problem to dd rectangles of size md×ndmd×nd which makes a result of
d⋅(md+nd−1)=m+n−dd⋅(md+nd−1)=m+n−d=m+n−gcd(m,n)=m+n−gcd(m,n)
And we can see, that the former result is a special case of the latter: the 'minus one' term is a 'minus GCD of sizes', since a GCD of coprime numbers is 11.
Chúc bạn học tốt nhớ cho mình 1 like nhé !
