SetMultiples
Member SRM 505 · 2010-11-01 · by ivan_metelsky
Member SRM 505 · 2010-11-01 · by ivan_metelsky · Math, Sorting
Problem Statement
Problem Statement
Suppose that S1 and S2 are sets of integer numbers. Let's call S2 a multiple of S1 if for each integer x from S1 there exist an integer y from S2 such that y is an integer multiple of x, i.e., y = k * x, where k is an integer.
You are givenlong s A, B, C, D. Consider a set S consisting of integers x such that A <= x <= B or C <= x <= D. Return the number of elements in the smallest subset of S that is a multiple of S.
You are given
Notes
- Since S is a subset of S and S is a multiple of S, the answer exists for any test case.
Constraints
- A will be between 1 and 10,000,000,000, inclusive.
- B will be between A and 10,000,000,000, inclusive.
- C will be between B + 1 and 10,000,000,000, inclusive.
- D will be between C and 10,000,000,000, inclusive.
Examples
0)
1 1 2 2 Returns: 1
Here S = {1, 2}. The subset {2} is a multiple of S because 2 is a multiple of both 1 and 2.
1)
1 2 3 4 Returns: 2
This time, S = {1, 2, 3, 4}. The subset {3, 4} is a multiple of S because 4 is a multiple of 1, 2 and 4, and 3 is a multiple of 3.
2)
2 3 5 7 Returns: 3
S = {2, 3, 5, 6, 7}. The solution is {5, 6, 7}.
3)
1 10 100 1000 Returns: 500
4)
1000000000 2000000000 9000000000 10000000000 Returns: 1254365078
Submissions are judged against all 159 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SetMultiples with a public method long long smallestSubset(long long A, long long B, long long C, long long D) · 159 test cases · 2 s / 256 MB per case