Connection Status:
Competition Arena > LCMSet

LCMSet

SRM 611 · 2013-12-22 · by cgy4ever

SRM 611 · 2013-12-22 · by cgy4ever · Math
Class Name: LCMSet
Return Type: String
Method Name: equal
Arg Types: (vector<int>, vector<int>)
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.


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.

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
0)
{2,3,4,12}
{2,3,4,6}
Returns: "Equal"

LCM(A) = LCM(B) = {2,3,4,6,12}

1)
{4,9}
{6,36}
Returns: "Not equal"

LCM(A) = {4,9,36}, LCM(B) = {6,36}

2)
{2,3,5,7,14,105}
{2,3,5,6,7,30,35}
Returns: "Equal"
3)
{2,3,5,7,14,105}
{2,3,5,6,7,30,36}
Returns: "Not equal"
4)
{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.

Submissions are judged against all 179 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LCMSet with a public method string equal(vector<int> A, vector<int> B) · 179 test cases · 2 s / 256 MB per case

Submitting as anonymous