Problem Statement
On the table you have a piece of paper. The paper has the shape of a rectangle with the integer dimensions A times B.
You also have a paper cutter. You want to cut your paper into one or more squares. You are going to do that by repeating the following steps:
- If there are some paper squares on the table, remove them from the table.
- If there is no paper left on the table, you are done and the process terminates.
- Make a single straight cut across the paper rectangle on the table in such a way that at least one of the two new pieces is a square.
It can be shown that:
- Whenever we reach step 3, there will always be exactly one paper rectangle on the table.
- In step 3 there will always be a unique way to make the cut. (More precisely, the sizes of the two pieces after we make the cut can always be uniquely determined.)
- For any dimensions of the starting paper rectangle the process will terminate after a finite number of cuts.
Given A and B, count and return the total number of cuts we will make while dividing the A times B rectangle into squares.
Definition
- Class:
- CutAwaySquares
- Method:
- countCuts
- Parameters:
- long, long
- Returns:
- long
- Method signature:
- long countCuts(long A, long B)
- (be sure your method is public)
Notes
- The correct answer will always fit into a signed 64-bit integer variable.
Constraints
- A will be between 1 and 10^18, inclusive.
- B will be between 1 and 10^18, inclusive.
Examples
47
47
Returns: 0
This paper is already a square. We remove it from the table and we are done. There were no cuts.
5
10
Returns: 1
We proceed as follows: Step 1: The only paper is a rectangle, we do nothing. Step 2: There is still a paper on the table, we do nothing. Step 3: We cut the 5x10 paper in half. (The cut is through the middle, parallel to the shorter sides.) This divides the paper into two 5x5 squares. Step 1: There are two squares on the table, we remove both of them. Step 2: The table is now empty, so the process ends here.
20
2
Returns: 9
In the first round we cut the paper into a 2x2 square and a 18x2 rectangle. Several similar rounds follow. In the last (9th) round in which we still make a cut we cut a 4x2 rectangle into two 2x2 squares.
42
22
Returns: 11
After two iterations of making a cut and then removing a square we get the situation from the previous example. Thus, this rectangle needs 2+9 = 11 cuts. When we are done, we'll have a 22x22 square, a 20x20 square, and ten 2x2 squares.
65455570134626
486227202717734097
Returns: 7565
6495899089
1218016714255684
Returns: 187598
9433417458107462
8202
Returns: 1150136242235
16287566828
3
Returns: 5429188944
26579951560186736
37521873889656
Returns: 791
207903028672120
20
Returns: 10395151433605
7589627891491
847619582580376
Returns: 265
5955
8539333666344
Returns: 1433977167
30037
60302464354981
Returns: 2007606127
62
834922219988
Returns: 13466487429
329604201
118093785
Returns: 88
2
1176
Returns: 587
33508779297
100112436463493
Returns: 3079
23807794064465
78435
Returns: 303535377
221263
1726826425317359
Returns: 7804406683
131731376252912984
445
Returns: 296025564613304
6
40
Returns: 8
16625940
66752839
Returns: 283
389181491112282234
879065
Returns: 442722086787
47
224
Returns: 13
34223
3287
Returns: 47
103
1398451633
Returns: 13577214
27879723551
78
Returns: 357432363
7689831499617753
544428872986
Returns: 14402
147727
31498
Returns: 40
298536205255686192
40798401006184210
Returns: 115
117016898053
8466097446185
Returns: 180
4
553706968792957575
Returns: 138426742198239396
49650675473
122332192137
Returns: 192
311
776952294014
Returns: 2498238942
2468
948484439087
Returns: 384313015
9718
19824664348698021
Returns: 2039994273409
27018810770191
5199534008
Returns: 5296
129520300
518727693961
Returns: 4182
1439049284205
34494067190365390
Returns: 24121
109199263726150987
219483597676
Returns: 497626
43892
35939763792845610
Returns: 818822650922
26463436507830136
16636122357
Returns: 1591397
43
9696100
Returns: 225499
516321097
7532073
Returns: 133
1
910
Returns: 909
1
175216328847456
Returns: 175216328847455
2639275021809211
12156675654323217
Returns: 296
3667
3066234685691
Returns: 836169855
1387594797912
8480338779
Returns: 427
37280187087350
1600539508977040
Returns: 191
6895788789
201
Returns: 34307422
8290239
1942112069
Returns: 285
1877115648
13727
Returns: 136781
336
12107
Returns: 72
9730312
350302
Returns: 125
2421094
2563
Returns: 967
1910233357978329
59943
Returns: 31867496805
235870241005
3334
Returns: 70746966
8778
42645783
Returns: 4884
8172962056130
65126820260953
Returns: 160
75325443487294705
27730532
Returns: 2716336081
118
7693
Returns: 79
39078
4917356394466
Returns: 125834424
6046260069765
8781913264788968
Returns: 1709
47804
35324775
Returns: 791
102
32
Returns: 10
5218638228
197706508419587
Returns: 37974
154070220539886887
503797881992
Returns: 305926
30232
9824962130949702
Returns: 324985516403
4022232680820846
30779660
Returns: 130678345
82856448355970
33115653858648
Returns: 235
289
1477918
Returns: 5134
990095588
167529231807
Returns: 277
3
234255587
Returns: 78085197
2424448528108172
15217208877656014
Returns: 123
1
6
Returns: 5
91
1
Returns: 90
113
679962137743023166
Returns: 6017364050823235
63939829894
28286934930463
Returns: 566
1039024750536
959939337077107207
Returns: 923994
3085
15807113357738688
Returns: 5123861704310
6674749
8
Returns: 834347
21004480
314769309
Returns: 151
1
22610970149505697
Returns: 22610970149505696
918249
331512780861912172
Returns: 361027108006
47
74777
Returns: 1590
5
41109
Returns: 8225
252889517302
383374
Returns: 659853
42697
135792837070
Returns: 3180431
197000162374479912
3
Returns: 65666720791493303
225711508160297
965627896036
Returns: 328
24
507178
Returns: 21137
1368293513725837
27
Returns: 50677537545408
8813906367172
10098508575
Returns: 938
58
401429
Returns: 6931
5715594051
23117
Returns: 247294
6128004
129904277956
Returns: 21247
11544545529369
102387403705398
Returns: 106
3296975265538
55
Returns: 59945004855
557435953878980
2907925
Returns: 191695500
2493501974028688
5230
Returns: 476769019911
103843466
687915762120553
Returns: 6624652
6669664536
57399
Returns: 116222
222626301127008
7089293450
Returns: 31464
3884852911258
280674768
Returns: 14045
52297110719435
157539816331225994
Returns: 3015
1167390329548950
1331024529588290
Returns: 21
484609598176664332
484609598176664332
Returns: 0
684490095417455112
228163365139151704
Returns: 2
958351798269635
1905185634790
Returns: 580
481683428309098335
7918083753026274
Returns: 65
59095980
19315136466362160
Returns: 326843491
2185770573097986
861920988154510
Returns: 36
228027460
1300
Returns: 175415
250115504176740
650300310859524
Returns: 5
2778432104717412
93071313342464028
Returns: 170
392817063144
90558325451533740
Returns: 230584
23807642433291
634870464887760
Returns: 28
98818770841
57
Returns: 1733662648
17563790768732157
59950390497
Returns: 292996
502614500551990272
494339207677514496
Returns: 368
12734446012277100
9249480153944400
Returns: 94
12184663417900
26048358476539950
Returns: 2215
197123118771916
306923
Returns: 642255972
11028526616448
9387137016576
Returns: 56
65490394629690657
11968884898071768
Returns: 113
11540237665599030
2151196813680
Returns: 5375
129977869672885555
21196444929680
Returns: 6202
330243466425
24848552925
Returns: 35
8640
35563560
Returns: 4128
56677900402045
28510409915932
Returns: 118
17464331128401224
185558518239263005
Returns: 14
949369397460439
949369397460439
Returns: 0
245933661604084
2106534064285
Returns: 200
86684083817353935
382323167645843325
Returns: 71
692536111974225
254329200
Returns: 2723047
331324573802651520
2511891184524540
Returns: 144
269623678460895558
105218996472544608
Returns: 8
3002
1925230
Returns: 649
539043590141
4312348721128
Returns: 7
223586599765101708
98318905761
Returns: 2274155
243770567852421925
358486129194738125
Returns: 10
288640119105964584
975547508596416
Returns: 302
695397085119699444
77266342791077716
Returns: 8
32442825636
831867324
Returns: 38
384924834581075565
384924834581075565
Returns: 0
47966986925648342
276687593749580
Returns: 184
3246837296136370
28042931323050
Returns: 126
542443
78702652221841492
Returns: 145089257725
156388054167276800
18300729742979200
Returns: 14
45309847645590925
604623244521511217
Returns: 42
17956036342524152
151965356
Returns: 118158813
18672203225724
239928475348940538
Returns: 12850
322342217820067
58998113575795
Returns: 44
20000000000000
2000000000000
Returns: 9
Watch out for integer overflow, A and B can be large. (This example is just a scaled version of Example 2, so it also requires 9 cuts.)
1000000000000000000
2
Returns: 499999999999999999
1000000000000000000
1
Returns: 999999999999999999
1
1000000000000000000
Returns: 999999999999999999
3
1000000007
Returns: 333333337
1000000000000000000
999999999
Returns: 1999999999
1000000000000000000
3
Returns: 333333333333333335
2
10000000000000000
Returns: 4999999999999999
100000000000000000
1
Returns: 99999999999999999
2
1000000000001
Returns: 500000000001