SetMultiples | Topcoder Archive

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 given longs 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.

Definition

Class:: SetMultiples
Method:: smallestSubset
Parameters:: long, long, long, long
Returns:: long
Method signature:: long smallestSubset(long A, long B, long C, long D)
(be sure your method is public)

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

```
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
```
```
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
```
```
3
```
```
5
```
```
7
```
```
Returns: 3
```
S = {2, 3, 5, 6, 7}. The solution is {5, 6, 7}.
```
1
```
```
10
```
```
100
```
```
1000
```
```
Returns: 500
```

1000000000

2000000000

9000000000

10000000000

Returns: 1254365078

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.