Hello Codeforces!↵
↵
Recently, I authored the problem **[Contest Wanderer](https://codeforces.me/gym/696136/problem/E)**. 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:↵
↵
$$\text{Answer} = \frac{N \times M}{L}$$↵
↵
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.↵
↵
$$\text{Row Cycle} = \frac{N}{\gcd(N, a)}$$↵
↵
**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.↵
↵
$$\text{Col Cycle} = \frac{M}{\gcd(M, b)}$$↵
↵
**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).↵
↵
$$L = \text{lcm}(\text{Row Cycle}, \text{Col Cycle})$$↵
↵
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](https://codeforces.me/contest/2217/problem/C)↵
↵
2. [Drazil and His Happy Friends](https://codeforces.me/problemset/problem/515/B)↵
↵
3. [Yet Another Counting Problem](https://codeforces.me/problemset/problem/1342/C)↵
↵
↵
Hope this approach makes modular arithmetic on grids a bit more intuitive! Let me know what you thought of the problem.
↵
Recently, I authored the problem **[Contest Wanderer](https://codeforces.me/gym/696136/problem/E)**. 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:↵
↵
$$\text{Answer} = \frac{N \times M}{L}$$↵
↵
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.↵
↵
$$\text{Row Cycle} = \frac{N}{\gcd(N, a)}$$↵
↵
**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.↵
↵
$$\text{Col Cycle} = \frac{M}{\gcd(M, b)}$$↵
↵
**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).↵
↵
$$L = \text{lcm}(\text{Row Cycle}, \text{Col Cycle})$$↵
↵
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](https://codeforces.me/contest/2217/problem/C)↵
↵
2. [Drazil and His Happy Friends](https://codeforces.me/problemset/problem/515/B)↵
↵
3. [Yet Another Counting Problem](https://codeforces.me/problemset/problem/1342/C)↵
↵
↵
Hope this approach makes modular arithmetic on grids a bit more intuitive! Let me know what you thought of the problem.
