Problem Statement
We are looking at the first quadrant of an infinite square grid. Its rows and columns are numbered starting from zero. Each cell (r,c) contains the number (max(r,c) mod 3).
Compute and return the sum of all cells (r,c) such that r1 <= r <= r2 and c1 <= c <= c2.
Definition
- Class:
- ModularQuadrant
- Method:
- sum
- Parameters:
- int, int, int, int
- Returns:
- long
- Method signature:
- long sum(int r1, int r2, int c1, int c2)
- (be sure your method is public)
Constraints
- 0 <= r1 <= r2 <= 10^9.
- 0 <= c1 <= c2 <= 10^9.
Examples
0
2
1
4
Returns: 13
We want rows 0 through 2 and columns 1 through 4. The corresponding part of the grid looks as follows: 2201 1201 1201
2
2
0
7
Returns: 10
Now we are computing the sum of a single row that looks as follows: 22201201
4
8
0
5
Returns: 37
222222 111111 000000 222222 111112
12
34
56
78
Returns: 529
0
0
1000000000
1000000000
Returns: 1
0
1000000000
0
1000000000
Returns: 1000000001333333334
0
0
0
0
Returns: 0
67135896
377792040
461908963
594466506
Returns: 41179815609707880
487125379
612881716
276411073
368797829
Returns: 11618220240015866
415062492
550232948
421352827
660953937
Returns: 32386991714537768
43925400
853713569
449395963
707195153
Returns: 208762735856573288
25404580
110011131
672708
283260218
Returns: 23908754972174256
517063356
850666235
587001530
777236130
Returns: 63462810832662413
9809442
985054800
875863262
965012962
Returns: 86942832097054525
338848790
609421724
247011036
459238762
Returns: 57423079114736490
255273357
561856451
385561480
551852547
Returns: 50982030353725816
259897950
474831180
35717065
602310784
Returns: 121779818536439614
401759007
769585354
379516815
738306335
Returns: 131972239300039559
367127108
645292643
598922922
617512215
Returns: 5170900703772201
210435486
818082095
256215401
846762737
Returns: 358844088167513078
782917677
902613028
37880462
982424200
Returns: 113057494494167012
134754154
358552528
105169864
389595010
Returns: 63653885558537209
411864481
621000790
545789166
579958392
Returns: 7146025893628200
271479000
872936870
104258888
696652797
Returns: 356299980043690209
936243973
946086475
243694079
995373586
Returns: 7398407805966856
750769163
907983561
234670474
359552046
Returns: 19633181445369627
505764849
799056097
118268043
830082628
Returns: 208768988401333609
447385546
649243544
379083493
724619612
Returns: 69749230102869932
307431950
936679871
829933621
943979838
Returns: 71763345724041080
256605994
869690042
596212365
868778923
Returns: 167106209364966540
280879785
989998540
383264903
571965507
Returns: 133811138148246976
43067572
607076112
335229332
519633099
Returns: 104005300021646642
604235495
837158197
279434604
424641141
Returns: 33821899324232214
557700496
784058147
237229314
858579682
Returns: 140647410992097321
122337491
651057817
673673332
903481341
Returns: 121504166194419270
222357206
407879373
271805617
521192987
Returns: 46266885834546658
648024763
994029812
160204725
599194165
Returns: 151892563921666491
16310367
476619356
182853533
587328861
Returns: 186183630269829651
673404583
863645037
88879941
817622289
Returns: 138636275955383657
80106251
285346811
548934239
872583032
Returns: 66425860252773995
587191332
668418986
511648895
840026799
Returns: 26673367204038660
467735815
861002056
392537040
986210305
Returns: 233471654033508878
35628518
815161857
284556008
652610126
Returns: 286910457056439656
691803009
965501521
555088476
653516178
Returns: 26939515850677936
723820366
976562440
506602156
981853232
Returns: 120115943431212134
685395201
760408746
338221218
857357003
Returns: 38942215841187688
23872914
890700442
260940257
619463997
Returns: 310778248259850161
226951148
371476397
463467161
930735750
Returns: 67532109786897500
197585684
742802513
189705944
504436336
Returns: 171596307286277481
213327221
988878479
105675226
137306116
Returns: 24531377369972660
146737412
784281966
611626153
842998321
Returns: 147510066409385919
369426272
566292666
116055547
421294032
Returns: 60091200319499462
286544298
476656188
485223
700751158
Returns: 133128880883044640
131400022
444604326
72117357
396477633
Returns: 101591034950674077
22249658
283733899
44780631
150794607
Returns: 27720984324043476
194539708
793651122
549388645
897188377
Returns: 208370790011410543
215981477
527189263
829866348
840829695
Returns: 3411878957983089
531174522
871544936
487039672
567230838
Returns: 27294700803143077
605166843
609173462
10723827
746288199
Returns: 2947126929484800
79290910
188036108
161670309
897404346
Returns: 80007544299792763
583518861
989836379
363292614
682389688
Returns: 129654731867113868
50128420
931030468
667919250
942251502
Returns: 241659842981288088
251793813
764765051
65750734
406657323
Returns: 174875275907186180
23852118
132229151
95121428
325052044
Returns: 24919198308619219
57866117
944087158
330353341
588255571
Returns: 228558383719009882
256750958
657829698
788143801
962589203
Returns: 69966343009556364
162354904
574330895
590480970
622510786
Returns: 13195515220177472
293303963
818650486
664632564
921594081
Returns: 134993839809056216
86654360
612929097
527479943
604472707
Returns: 40519347176942060
367988208
597560671
56030499
123045707
Returns: 15384846588589767
443968465
448443766
379828288
973463063
Returns: 2656694901794120
325142223
605934918
815748422
906551299
Returns: 25496784918179088
525333703
641733357
68221557
149950278
Returns: 9513195044390910
125699083
545326953
495279163
969905990
Returns: 199166645739385865
701102584
844881430
487227965
884403724
Returns: 57105472733296156
19196099
466629860
605515027
869380778
Returns: 118062446527752786
560627570
819709817
71072587
839253913
Returns: 199022145646698828
308839297
847423726
756726466
841539667
Returns: 45679069999102726
526350671
539442012
122544572
810623578
Returns: 9007877594929832
263195265
378160092
355526281
854968508
Returns: 57418289937832404
179226442
496671190
24260175
631062846
Returns: 192626321693939496
105426212
720412488
493352292
494488687
Returns: 698867556554015
297197665
685081509
585103878
736604806
Returns: 58764762507034037
739996155
746550455
25537871
986463310
Returns: 6298194574502207
203243637
601508804
729714784
884873256
Returns: 61794215315968464
43901203
308222626
282674977
828718827
Returns: 144331088245732058
518276962
582239740
73514838
411998379
Returns: 21650347992083218
775694911
843957081
117075129
944031161
Returns: 56449814156881700
559272524
761348627
633503745
643082351
Returns: 1935607597078604
512516892
576767593
799221060
849100512
Returns: 3204789806375304
388654383
621118347
334682124
442484489
Returns: 25060165400712300
733157853
826768666
962200196
964545183
Returns: 219516235500232
219977310
786368716
98188879
679160796
Returns: 329057501635597870
110252490
550176498
327488403
868789569
Returns: 238131379097323859
357293695
434950847
578737879
897908491
Returns: 24785881126844789
386678572
913854417
116822057
876386673
Returns: 400424119232168914
100051728
917869312
668324192
798837166
Returns: 106735805938656725
387115369
457550043
53950146
375574708
Returns: 22653521566922025
625812828
928943728
60640904
993976201
Returns: 282922769050584307
420753700
680685373
287670031
866619587
Returns: 150487327599212310
226141678
273090581
224634685
311090680
Returns: 4059014273585012
499291494
913802966
710090537
881514056
Returns: 71057016221408696
321600643
878068838
478078314
832904610
Returns: 197449549346747973
340861581
472931687
724232338
928574706
Returns: 26987518538463483
58810011
166727022
515073838
623077931
Returns: 11655479216164140
660746
29553320
453916726
930045747
Returns: 13756593477811650
491132366
558585770
470167904
659341082
Returns: 12760375169126830
8
45
55
70
Returns: 608
58
73
32
43
Returns: 192
49
65
50
78
Returns: 498
5
53
3
84
Returns: 4036
0
13
33
61
Returns: 392
69
92
1
40
Returns: 960
54
72
29
30
Returns: 36
65
66
45
56
Returns: 24
4
30
47
71
Returns: 702
88
91
45
76
Returns: 128
43
71
73
97
Returns: 725
25
30
93
100
Returns: 42
4
16
12
42
Returns: 392
46
74
49
65
Returns: 519
32
69
12
83
Returns: 2748
29
89
27
42
Returns: 982
60
95
14
98
Returns: 3108
53
77
45
86
Returns: 1091
36
98
30
71
Returns: 2694
33
45
68
72
Returns: 65
0
1000000000
1
1000000000
Returns: 1000000000333333334
12321
999991548
12312
999991548
Returns: 999958464764636208
1
1000000000
1
1000000000
Returns: 999999999333333334
0
987654321
0
987654321
Returns: 975461059106843469
3
1000000000
233
1000000000
Returns: 999999765333333952
1
88888888
1
88888888
Returns: 7901234350617286
0
987654321
0
900000000
Returns: 888888890187654321
1
579
7
679
Returns: 389285
11
999999987
111
999999987
Returns: 999999853333336144
3
8
5
9
Returns: 31
250000000
500000000
750000000
1000000000
Returns: 62500000250000000
763481
507994224
139595265
336998086
Returns: 100128780000325903
0
3
0
3
Returns: 13
123456789
300000000
500000000
1000000000
Returns: 88271606176543212