NonCoprimeGraph
2016 TCO Semi 1 · 2016-03-24 · by cgy4ever
2016 TCO Semi 1 · 2016-03-24 · by cgy4ever · Graph Theory, Math
Problem Statement
Problem Statement
Two positive integers are called coprime (or relatively prime) if their greatest common divisor is 1.
For example, 10 and 21 are coprime, but 15 and 21 are not coprime as they are both divisible by 3.
Let G be a simple undirected graph with the following properties:
You are given theint n.
You are also given int s s and t.
Find and return the length of the shortest path between the vertices s and t.
If there is no such path, return -1 instead.
Let G be a simple undirected graph with the following properties:
- G has n vertices, numbered 1, 2, ..., n.
- For each pair (i,j) such that i != j, the vertices i and j are connected by an edge if and only if the numbers i and j are not coprime.
You are given the
Constraints
- n will be between 1 and 1,000,000,000, inclusive.
- s will be between 1 and n, inclusive.
- t will be between 1 and n, inclusive.
Examples
0)
10 8 9 Returns: 2
The numbers 8 and 9 are coprime, thus there is no direct edge between the vertices 8 and 9. There is a unique shortest path of length 2: the path 8 - 6 - 9.
1)
10 6 9 Returns: 1
The numbers 6 and 9 are both divisible by 3. As they are not coprime, there is a direct edge between the vertices 6 and 9. Obviously, this edge is the shortest path that connects 6 and 9.
2)
100 89 97 Returns: -1
3)
100 97 97 Returns: 0
4)
1 1 1 Returns: 0
Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NonCoprimeGraph with a public method int distance(int n, int s, int t) · 106 test cases · 2 s / 256 MB per case