GCDLCMEasy | Topcoder Archive

Problem Statement

Your task is to find n positive integers. We will label them x[0] through x[n-1].

We will give you some information about these integers. Namely, for some pairs of integers we will tell you both their greatest common divisor (GCD) and their least common multiple (LCM).

You are given the int n and four int[]s: A, B, G, and L. These int[]s will all have the same number of elements. Their meaning is as follows: For each valid i, the integers x[ A[i] ] and x[ B[i] ] must have the greatest common divisor G[i] and the least common multiple L[i].

Return "Solution exists" (quotes for clarity) if there is at least one way to choose x[0] through x[n-1] so that all requirements are satisfied. Otherwise, return "Solution does not exist".

Definition

Class:: GCDLCMEasy
Method:: possible
Parameters:: int, int[], int[], int[], int[]
Returns:: String
Method signature:: String possible(int n, int[] A, int[] B, int[] G, int[] L)
(be sure your method is public)

Notes

The greatest common divisor (GCD) of two positive integers x and y is the largest positive integer z such that z divides x and at the same time z divides y.
The least common multiple (LCM) of two positive integers x and y is the smallest positive integer z such that x divides z and at the same time y divides z.
For example, the GCD of 10 and 15 is 5, and the LCM of 10 and 15 is 30.

Constraints

n will be between 1 and 500, inclusive.
A will contain between 1 and 500 elements, inclusive.
A and B will contain the same number of elements.
A and G will contain the same number of elements.
A and L will contain the same number of elements.
Each element in A will be between 0 and n-1, inclusive.
Each element in B will be between 0 and n-1, inclusive.
For each i, A[i] and B[i] will be different.
Each element in G will be between 1 and 10,000, inclusive.
Each element in L will be between 1 and 10,000, inclusive.

Examples

```
4
```
```
{0,1,2,3}
```
```
{1,2,3,0}
```
```
{6,6,6,6}
```
```
{12,12,12,12}
```
```
Returns: "Solution exists"
```
We have 4 unknown integers: x[0], x[1], x[2], and x[3]. The given A, B, G, and L encode the following information: The GCD of x[0] and x[1] must be 6 and their LCM must be 12. The GCD of x[1] and x[2] must be 6 and their LCM must be 12. The GCD of x[2] and x[3] must be 6 and their LCM must be 12. The GCD of x[3] and x[0] must be 6 and their LCM must be 12. There are two valid solutions. In one of them, x[0] = x[2] = 6 and x[1] = x[3] = 12.

{0,1,2,3,4}

{1,2,3,4,0}

{6,6,6,6,6}

{12,12,12,12,12}

Returns: "Solution does not exist"

```
2
```
```
{0,0}
```
```
{1,1}
```
```
{123,123}
```
```
{456,789}
```
```
Returns: "Solution does not exist"
```
The LCM of x[0] and x[1] cannot be 456 and 789 at the same time.
```
2
```
```
{0}
```
```
{1}
```
```
{1234}
```
```
{5678}
```
```
Returns: "Solution does not exist"
```
The LCM of x[0] and x[1] must always be a multiple of their GCD.

{0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4}

{1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5}

{2, 2, 3, 3, 1, 2, 5, 1, 5, 1, 7, 7, 3, 5, 7}

{30, 42, 30, 42, 210, 70, 30, 210, 70, 210, 42, 70, 105, 105, 105}

Returns: "Solution exists"

There is one solution: {6, 10, 14, 15, 21, 35}.

{0}

{1}

{10000}

{10000}

Returns: "Solution exists"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.