RabbitsAndCakes | Topcoder Archive

Problem Statement

Some rabbits are going to gather and hold a cake party. The exact number of rabbits participating in the party and the exact number of cakes prepared for the party are not determined yet. The rabbits say they want to divide the cakes in the following way.

Let the number of rabbits be R and the number of cakes C. All C cakes are the same size. Each cake may be cut into two pieces (of possibly non-equal sizes) or kept uncut. Then the cakes and pieces of cake are distributed among the rabbits, so that all of the rabbits get the same amount of cake (that is, C/R cakes).

You know that R is between minR and maxR, inclusive, and C is between minC and maxC, inclusive. Return the number of pairs (R, C) for which the division of cakes described above is possible.

Definition

Class:: RabbitsAndCakes
Method:: getNumber
Parameters:: int, int, int, int
Returns:: long
Method signature:: long getNumber(int minR, int maxR, int minC, int maxC)
(be sure your method is public)

Constraints

minR will be between 1 and 1,000,000, inclusive.
maxR will be between minR and 1,000,000, inclusive.
minC will be between 1 and 1,000,000, inclusive.
maxC will be between minC and 1,000,000, inclusive.

Examples

```
4
```
```
5
```
```
3
```
```
3
```
```
Returns: 1
```
For (R, C) = (4, 3) the division is possible. One possible way is as follows: Cut the first cake into two pieces: (a) of size 3/4 and (b) of size 1/4. Cut the second cake into two pieces: (c) of size 3/4 and (d) of size 1/4. Cut the third cake into two pieces: (e) of size 1/2 and (f) of size 1/2. Then: The first rabbit can take piece (a). The second rabbit can take pieces (b) and (e). The third rabbit can take piece (c). The fourth rabbit can take pieces (d) and (f). For (R, C) = (5, 3) the division is impossible.
```
2
```
```
2
```
```
1
```
```
1000
```
```
Returns: 1000
```
```
1
```
```
1000
```
```
2
```
```
2
```
```
Returns: 4
```
```
4
```
```
7
```
```
4
```
```
7
```
```
Returns: 14
```

Returns: 6848769959

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.