number theory in a graph

Revision en1, by bhikkhu, 2015-06-14 19:13:40

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://codeforces.net/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://codeforces.net/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.

Tags number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English bhikkhu 2015-06-14 19:13:40 1003 Initial revision (published)