LCMSetEasy | 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.

You are given a int[] S and an int x. Find out whether we can select some elements from S in such a way that their least common multiple will be precisely x. Formally, we are looking for some s1, s2, ..., sK, K >= 1, such that each si belongs to S, and x=lcm(s1, s2, ..., sK). Return "Possible" if such elements of S exist, and "Impossible" if they don't.

Definition

Class:: LCMSetEasy
Method:: include
Parameters:: int[], int
Returns:: String
Method signature:: String include(int[] S, int x)
(be sure your method is public)

Constraints

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

Examples

```
{2,3,4,5}
```
```
20
```
```
Returns: "Possible"
```
We can obtain 20 in multiple ways. One of them: 20 = lcm(4, 5).
```
{2,3,4}
```
```
611
```
```
Returns: "Impossible"
```
If S={2,3,4}, the only values we can obtain are 2, 3, 4, 6, and 12.
```
{2,3,4}
```
```
12
```
```
Returns: "Possible"
```

{1,2,3,4,5,6,7,8,9,10}

Returns: "Possible"

{100,200,300,400,500,600}

Returns: "Possible"

{100,200,300,400,500,600}

Returns: "Impossible"

{1000000000,999999999,999999998}

999999999

Returns: "Possible"

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.