Can anyone please tell me the approach of this question https://www.codechef.com/ENFE2019/problems/DIETCOKE .The answer is coming by m+n-gcd(m,n).Logic??

general
1

given a matrix of size m X n . A line is passing from diagonal . You need to calculate the total cells falling through that line
The answer is coming by m+n-gcd(m,n).Logic??

2

First of all, all credits goes to this StackOverflow beautiful explanation.

I am putting here all together with some example.Example Images

You can easily observe that if N, M doesn’t have a common factor then the diagonal will not go through any of the intersections.

Now here is explanation :

First, if M and N have no common factor then the diagonals would not go through any intersections, so each time it crosses a horizontal or vertical grid line, it adds 1 to the number of squares touched. nd to get from the top left to bottom right, it must pass through N-1 vertical grid line (total lines are N+1 so leave 1^{st} and last) and M-1 horizontal grid lines. Counting the original square in the top left (it will always be in our answer), this gives a total of 1 (top-left square) + (N - 1) + (M - 1) = N + M - 1.

This formula applies to first and second diagrams.

Now suppose that N and M have a common factor. Let q= (N,M) be the largest common factor (GCD) of N and M. Then the new size N/q and M/q have no common factor, so we can break the problem up into q smaller rectangles strung along the diagonal, each of size N/q \times M/q and in each such rectangle the number of squares visited is N/q + M/q - 1. So the total number of squares visited is q \times (N/q + M/q -1) = N + M - q.

Hence in all cases the number of squares touched is

N + M - (N,M)