PROBLEM LINK:
Author: Soham Chakrabarti
Tester: Soham Chakrabarti
DIFFICULTY:
Cakewalk
PREREQUISITES:
Math
PROBLEM:
You are provided an area divided into M x N blocks.
A straight, red line has been drawn from one corner to another (left to right).
Find the number of blocks that contains the red line on it.
EXPLANATION:
First, suppose that N and M have no common factor. Then the diagonal line doesn’t go through any intersections, so each time it crosses a horizontal or vertical grid line, it adds 1 to the number of squares touched. And to get from the top left to the bottom right, it must pass through N−1 vertical grid lines and M−1 horizintal grid lines. Counting the orginal square in the top left, this gives a total of 1+(N−1)+(M−1)=N+M−1 squares touched. This formula applies to your first and second diagrams.
Now suppose that N and M have a common factor. Let q=(N,M) be the largest common factor of N and M. Then 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×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×(N/q+M/q−1)=N+M−q.
Hence in all cases the number of squares touched is
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s and Tester’s solution can be found
Link