Hello Codeforces!

Recently, I authored the problem Contest Wanderer. The problem asks a very simple question: If you start walking on an $$$N \times M$$$ grid that wraps around its boundaries (moving $$$a$$$ steps down and $$$b$$$ steps right), how many unique starting positions do you need to pick to guarantee you step on every single cell in the room?

Many people look at grid problems and immediately think of Grid Covering, DP with Broken Profiles, or Bipartite Matching. But this problem is a trap. It is purely Number Theory and Modular Arithmetic.

Visualizing the Cycle:

Two examples:

1. $$$4 \times 6$$$:

2. $$$3 \times 6$$$:

Things to notice:

-> No matter where you start on this grid, your path will eventually loop back to your exact starting coordinate.

-> Because the grid is perfectly symmetric, every single cycle will have the exact same length, L. (Note: this is the best point to make it intuitive, try some examples yourselves if you find it interesting).

If we know the length of one cycle, the minimum number of starting coordinates we need is simply:

So, how do we find $$$L$$$ without simulating it?

Let's think in 1D:

1. The Row Cycle

Imagine just the rows as a single vertical column. You are on a grid of height $$$N$$$, and every step you move $$$a$$$ units down.

If you are at row $$$0$$$, you will return to row $$$0$$$ only when your total distance traveled downward is a perfect multiple of $$$N$$$. The smallest number of steps required to hit a multiple of $$$N$$$ while taking steps of size $$$a$$$ is dictated by the Greatest Common Divisor.

2. The Column Cycle

The exact same logic applies to the columns. Imagine the columns as a horizontal row of width $$$M$$$, moving $$$b$$$ units right per step.

Bringing it Together:

Here is where the mathematical intuition clicks. For the path to return to the exact $$$(0,0)$$$ coordinate on the 2D grid, both the row and the column must hit $$$0$$$ at the exact same time.

If the row returns to $$$0$$$ every 4 steps, and the column returns to $$$0$$$ every 6 steps, the first time they both return to $$$0$$$ together is at step 12. Mathematically, this alignment of two independent cycles is just their Least Common Multiple (LCM).

The Final $$$O(\log(\min(N, M)))$$$ Solution

With this visualization in mind, the code becomes incredibly simple. We can find the answer instantly using standard gcd operations:

#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}

void solve() {
    long long N, M, a, b;
    cin >> N >> M >> a >> b;
    
    // Calculate 1D cycles
    long long rowCycle = N / gcd(N, a);
    long long colCycle = M / gcd(M, b);
    
    long long L = lcm(rowCycle, colCycle);
    
    long long totalCells = N * M;
    cout << totalCells / L << "\n";
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

Other problems with similar concept

1. Grid Covering

2. Drazil and His Happy Friends

3. Yet Another Counting Problem

Hope this approach makes modular arithmetic on grids a bit more intuitive! Let me know what you thought of the problem.