LCMSet | Topcoder Archive

Problem Statement

For any non-empty sequence of positive integers s1, s2, ..., sK their least common multiple is the smallest positive integer that is divisible by each of the given numbers. We will use "lcm" to denote the least common multiple. For example, lcm(3) = 3, lcm(4,6) = 12, and lcm(2,5,7) = 70.

Given a sequence S, we now define the set LCM(S) as follows: LCM(S) = { lcm(s1, s2, ..., sk) | s1, s2, ..., sk belong to S, k > 0}. In words: LCM(S) is the set of all values that can be obtained by selecting some elements of S and computing their least common multiple. For example, for S={2,3,4} we have LCM(S)={2,3,4,6,12}.

You are given two int[]s A and B. Return "Equal" if LCM(A) = LCM(B), and "Not equal" otherwise.

Definition

Class:: LCMSet
Method:: equal
Parameters:: int[], int[]
Returns:: String
Method signature:: String equal(int[] A, int[] B)
(be sure your method is public)

Constraints

A will contain between 1 and 50 elements, inclusive.
B will contain between 1 and 50 elements, inclusive.
Each element in A will be between 2 and 1,000,000,000, inclusive.
Each element in B will be between 2 and 1,000,000,000, inclusive.
Elements in A will be distinct.
Elements in B will be distinct.

Examples

```
{2,3,4,12}
```
```
{2,3,4,6}
```
```
Returns: "Equal"
```
LCM(A) = LCM(B) = {2,3,4,6,12}
```
{4,9}
```
```
{6,36}
```
```
Returns: "Not equal"
```
LCM(A) = {4,9,36}, LCM(B) = {6,36}

{2,3,5,7,14,105}

{2,3,5,6,7,30,35}

Returns: "Equal"

{2,3,5,7,14,105}

{2,3,5,6,7,30,36}

Returns: "Not equal"

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}

Returns: "Equal"

Note that some of the numbers in the sets LCM(A) and LCM(B) can be huge. In this case, the largest number in LCM(A) is 2305567963945518424753102147331756070.

{999999999,1953125,512,1000000000}

{999999999,1953125,512}

Returns: "Equal"

{999999998,999999999,1000000000}

{999999999,1000000000}

Returns: "Not equal"

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.