RabbitsAndCakes

TCO13 Semifinal 1 · 2013-02-19 · by lyrically

TCO13 Semifinal 1 · 2013-02-19 · by lyrically · Math

Show categories

Class Name: RabbitsAndCakes

Return Type: long

Method Name: getNumber

Arg Types: (int, int, int, int)

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.

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

64716
101247
99867
287365
Returns: 6848769959

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

Coding Area

Language: C++17 · define a public class RabbitsAndCakes with a public method long long getNumber(int minR, int maxR, int minC, int maxC) · 56 test cases · 2 s / 256 MB per case