GCDGraph

SRM 703 · 2016-12-04 · by cgy4ever

SRM 703 · 2016-12-04 · by cgy4ever · Graph Theory, Math

Show categories

Class Name: GCDGraph

Return Type: String

Method Name: possible

Arg Types: (int, int, int, int)

Problem Statement

You are given four ints: n, k, x, and y.

The ints n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and only if gcd(i, j) > k. Here, gcd(i, j) denotes the greatest common divisor of i and j.

The ints x and y are the numbers of two (not necessarily distinct) vertices in our graph. Return "Possible" if it is possible to travel from x to y by following the edges of our graph. Otherwise, return "Impossible".

In other words, return "Possible" if our graph contains a path that connects the nodes x and y, and "Impossible" if there is no such path.

Constraints

n will be between 2 and 1,000,000, inclusive.
k will be between 0 and n, inclusive.
x and y will be between 1 and n, inclusive.

Examples

12
2
8
9
Returns: "Possible"

We have a graph with n = 12 nodes. As k = 2, vertices i and j are connected by an edge if and only if gcd(i, j) is strictly greater than 2. In this graph it is possible to travel from node 8 to node 9. One possible path: 8 -> 4 -> 12 -> 9.

12
2
11
12
Returns: "Impossible"

This is the same graph as in Example 0, but now we are interested in another pair of nodes. It is not possible to travel from node 11 to node 12. In particular, in our graph node 11 is an isolated node because for any other node x we have gcd(11, x) = 1.

12
2
11
11
Returns: "Possible"

A node is always reachable from itself.

10
2
8
9
Returns: "Impossible"

1000000
1000
12345
54321
Returns: "Possible"

Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GCDGraph with a public method string possible(int n, int k, int x, int y) · 117 test cases · 2 s / 256 MB per case