LCMSetEasy
SRM 611 · 2013-12-22 · by cgy4ever
SRM 611 · 2013-12-22 · by cgy4ever · Math
Problem Statement
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 aint[] 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.
You are given a
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"
Submissions are judged against all 139 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LCMSetEasy with a public method string include(vector<int> S, int x) · 139 test cases · 2 s / 256 MB per case