We have two groups of nodes, group A consisting of N items, group B consisting of M items. There is an edge connecting node a of group A and node b of group B, where

a = i mod N

b = i mod M

where i is an integer.

Image description of the problem (http://mirror.codeforces.com/predownloaded/5a/b5/5ab5c142069cd987264c765383e682f622a7f0bf.png)

We need to find for each node if there is a path connecting to another node in the graph.

To create the adjacency matrix, I iterated from i from 0 to LCM(N,M) — 1, since after that, we would get same edge pairs. Now, discarding this approach, how can one find mathematically, if two nodes of the graph are connected by a path or not? This is actually my trimmed version of this problem (http://mirror.codeforces.com/problemset/problem/515/B)

The tutorial doesnot explain the GCD method to get O(N + M) complexity. I tried myself but couldnot go far. Any help regarding how it was derived will be immensely helpful.