Problem Statement
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
64716
101247
99867
287365
Returns: 6848769959
1
1
1
1
Returns: 1
1
1
1
1000000
Returns: 1000000
1
1
1000000
1000000
Returns: 1
1
1000000
1
1
Returns: 2
1
1000000
1
1000000
Returns: 500013470034
1
1000000
1000000
1000000
Returns: 1000000
1000000
1000000
1
1
Returns: 0
1000000
1000000
1
1000000
Returns: 49
1000000
1000000
1000000
1000000
Returns: 1
3150
990534
4280
991932
Returns: 488857589364
7551
990298
9580
992783
Returns: 485350121641
6994
998748
6059
997024
Returns: 490094066141
581
999075
6301
994347
Returns: 493783422892
3950
997352
5439
991877
Returns: 488013091811
997401
998551
996045
998792
Returns: 949718
991388
999991
993774
998504
Returns: 22523192
993004
996413
998706
999175
Returns: 1602700
998405
999514
995079
996131
Returns: 343
997580
999608
999387
999673
Returns: 558910
8984
8984
6738
6738
Returns: 1
459160
459160
454745
454745
Returns: 1
884617
884617
884616
884616
Returns: 1
883008
883008
882336
882336
Returns: 1
472992
472992
472984
472984
Returns: 1
316334
741572
352213
713049
Returns: 78052884439
932427
968987
201035
968987
Returns: 668880427
779640
963654
443736
830376
Returns: 1288121803
659606
918455
849488
918064
Returns: 15373711738
605904
948246
48278
605826
Returns: 473393
606793
846424
581509
900000
Returns: 41553341472
167224
808593
76676
769601
Returns: 181437978770
472014
906134
868025
905942
Returns: 15735236349
315721
444379
772064
982217
Returns: 27038203486
477962
982968
556865
728565
Returns: 28290712144
721280
786167
334430
441894
Returns: 32444
475466
733459
889567
914241
Returns: 6366001950
62830
830710
427847
472394
Returns: 17253648491
95455
175523
90151
449469
Returns: 25141032491
33276
880261
33217
515366
Returns: 116212538776
134235
824175
33658
244311
Returns: 6060125271
440604
747262
96620
440594
Returns: 373559
796871
986696
116891
618685
Returns: 145643
538579
938032
272451
468804
Returns: 287532
179650
684816
201893
340319
Returns: 12662008157
203744
299774
213349
441950
Returns: 18219141404
436833
761401
576893
665752
Returns: 16394928127
337760
740383
454445
737661
Returns: 73156705682
442581
684579
420452
979676
Returns: 100698034162
685384
844770
673072
844740
Returns: 12699292256
337903
875757
337900
954952
Returns: 187246584655
452466
771912
452448
872178
Returns: 83056942043