JOIN
Get Time

   Problem Statement  

 Problem Statement for LCMSetEasy

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

0)
    
{2,3,4,5}
20
Returns: "Possible"
We can obtain 20 in multiple ways. One of them: 20 = lcm(4, 5).
1)
    
{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)
    
{2,3,4}
12
Returns: "Possible"
3)
    
{1,2,3,4,5,6,7,8,9,10}
24
Returns: "Possible"
4)
    
{100,200,300,400,500,600}
2000
Returns: "Possible"
5)
    
{100,200,300,400,500,600}
8000
Returns: "Impossible"
6)
    
{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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 611 Round 1 - Division II, Level Two