Problem Statement
Vegard and Bard have some packs of sweets: for each i between A and B, inclusive, they have one pack that contains i sweets. The pair (A, B) is called fair if Vegard and Bard can divide the packs among themselves in such a way that each of them gets the same total number of sweets.
Count all fair pairs (A, B) such that A <= B, loA <= A <= hiA, and loB <= B <= hiB.
Definition
- Class:
- FairSplit
- Method:
- count
- Parameters:
- int, int, int, int
- Returns:
- long
- Method signature:
- long count(int loA, int hiA, int loB, int hiB)
- (be sure your method is public)
Constraints
- 1 <= loA <= hiA <= 2,000,000,000.
- 1 <= loB <= hiB <= 2,000,000,000.
Examples
7
7
1
15
Returns: 3
A must be 7, and B must be between 1 and 15, inclusive. There are three fair pairs that match these constraints: (7,10), (7,13), and (7,14). In the first case, Vegard can take 7+10 sweets. In the second case, Vegard can take 10+12+13 sweets. In the third case, Vegard can take 7+10+12+13 sweets. We can easily verify that in each of those cases Bard will get the same number of sweets as Vegard.
101
200
1
100
Returns: 0
For these constraints we cannot have A <= B, so there is no fair pair that matches these constraints.
1
4
5
10
Returns: 11
4
17
12
33
Returns: 129
1
2000000000
1
2000000000
Returns: 999970186260287400
65
361
441
567
Returns: 18859
465
585
264
352
Returns: 0
396
525
402
631
Returns: 9688
42
815
429
675
Returns: 60216
25
981
1
105
Returns: 1349
271
966
812
989
Returns: 53385
494
742
10
560
Returns: 604
836
940
324
921
Returns: 997
438
582
236
244
Returns: 0
527
536
368
453
Returns: 0
248
981
35
575
Returns: 23792
384
734
362
705
Returns: 22440
351
616
572
589
Returns: 1856
201
781
245
808
Returns: 85600
747
861
937
958
Returns: 1264
37
129
101
342
Returns: 10834
372
593
393
521
Returns: 4206
554
833
100
259
Returns: 0
665
893
233
903
Returns: 11308
716
950
343
866
Returns: 3958
224
483
113
763
Returns: 50809
427
792
362
620
Returns: 7446
692
894
294
901
Returns: 8447
792
830
245
829
Returns: 171
569
945
268
366
Returns: 0
546
579
42
496
Returns: 0
320
577
405
799
Returns: 41326
267
968
532
748
Returns: 37835
227
819
117
621
Returns: 35182
643
862
213
389
Returns: 0
260
498
619
986
Returns: 43976
572
948
153
455
Returns: 0
16
175
561
643
Returns: 6640
780
824
77
85
Returns: 0
273
524
638
833
Returns: 24696
488
560
802
822
Returns: 766
375
447
778
941
Returns: 5986
34
623
272
921
Returns: 156867
624
660
530
967
Returns: 5542
691
932
484
937
Returns: 12123
1370790403
1520817494
676442437
1714714007
Returns: 20169045068509274
47745830
1781400886
521880515
1238927995
Returns: 298517251418940611
453902297
742952795
926934323
1861471501
Returns: 135064218962001160
395171369
1485605028
379411890
1008872673
Returns: 94149260291498362
426654444
1977756960
211350453
274612233
Returns: 0
293474826
1568563934
1223252307
1685996643
Returns: 265203654756648616
738852545
1132585333
232111096
842588065
Returns: 2688806727900904
573088597
953312378
970447
1401502318
Returns: 121343529718639241
262800045
889208654
144234715
792955267
Returns: 70260117411413254
44499317
567467799
89561263
301589215
Returns: 16014696045022217
389079417
1587302246
1098777292
1794376755
Returns: 357068481368434881
431962956
1054378528
1659732698
1681659392
Returns: 6823758216210618
1062349046
1743089874
974079345
1134461677
Returns: 1298863540738150
1210333687
1218346925
21447656
1492576399
Returns: 1114646535664742
158581822
376072218
323340620
1794808694
Returns: 159319439409045948
1167037724
1979672759
726585229
1364779378
Returns: 9771924273256032
100256842
1862060938
1335838502
1884503006
Returns: 414081663230803113
503587628
1529530104
131501469
813314647
Returns: 23978742470259700
47704238
264458304
190242857
650104090
Returns: 48460854176845835
115732235
1888174317
660706684
1176511144
Returns: 207055896005748827
513501918
1315659397
1576287603
1925178407
Returns: 139932684466985700
324709810
1148661792
1180961942
1245021574
Returns: 26391030820301120
586607927
1637300974
1329265129
1843188164
Returns: 246260230133470041
173308721
1225858196
1054959888
1208945415
Returns: 73806056094427057
735976418
1195121344
112061000
246091415
Returns: 0
887936932
896887533
759656578
1946926127
Returns: 4719133394838746
650284448
1211869838
1631496846
1813102599
Returns: 50993569183969907
1050667407
1283466715
136443116
299900557
Returns: 0
251398168
1090653907
990558327
1939811982
Returns: 395826893595444751
1402205169
1689762861
974455932
1768807449
Returns: 32031645113425169
38392199
933259721
1211030056
1738761558
Returns: 236124891449338534
1121255141
1639419635
142145176
1678507828
Returns: 77241056302482784
617678595
1694847454
1513452934
1683079335
Returns: 83163377879209102
1052701344
1078884026
245089146
1621247158
Returns: 7271216810208336
526390531
756320185
711052564
1709937017
Returns: 114323676129625011
358452885
993342382
48520351
1262125694
Returns: 186086845865894806
210852425
1440824977
986704585
988977375
Returns: 882930581753962
594395331
1370163019
1170207758
1473209614
Returns: 107530435600421176
1479992312
1493100912
51075743
1972926622
Returns: 3187628036902164
406487276
1203017609
1459429569
1769746513
Returns: 123588429923354814
87802408
616445253
565349956
1657437655
Returns: 288008871266218604
1036553925
1164479481
147029677
823996760
Returns: 0
1551389824
1687914164
234150259
1888062323
Returns: 18319524641315276
1118545049
1522697255
1267007491
1286164703
Returns: 1513470782683116
1025033786
1153535187
1598442121
1698201025
Returns: 6409579577242406
777308768
1242236695
669364250
884968979
Returns: 2896129105056143
1466315708
1653537334
1924400394
1929090368
Returns: 439032375044663
439954621
1572737434
196377760
1358321593
Returns: 210835863585328367
220504982
1100352998
654976807
1737579139
Returns: 426666190095211966
714587391
869901695
1157475760
1795816984
Returns: 49571761856861812
773357145
1827708836
233644115
1752773347
Returns: 239796733530623620
200103458
1835738626
1336648385
1597674333
Returns: 165362498195241617
774230739
915100088
107900294
751149417
Returns: 0
1251625657
1857887457
121281810
1987952403
Returns: 131303113386179590
841507402
1361370748
575340064
1733239176
Returns: 164216251206497274
452283357
546181163
449269372
622181362
Returns: 5771276909299787
998582989
1827605933
1420181076
1763028114
Returns: 101651015396786652
643201288
1756137677
956156630
1665809221
Returns: 236933677721218359
681723164
945863375
1448464678
1857149413
Returns: 53975036404102016
117620023
333454045
1030147677
1246155863
Returns: 23310958000573150
12
123123
23
123123131
Returns: 7575163202073
5757
2000000000
4343
1900000000
Returns: 902466925923446618