Problem Statement
We are on an infinite horizontal plane. For each pair of integers (x, y) such that |x| <= N and |y| <= N there is an animal sitting on the point (x, y). The animal on (0, 0) is a cat and all other animals are mice.
The cats wants to run away in some direction, that is, along some infinite ray that starts at (0, 0). Along the way the cat will catch and eat all the mice it encounters.
The cat wants to catch exactly C mice. Return the number of different directions the cat can choose.
Definition
- Class:
- CatAndMice
- Method:
- countDirections
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long countDirections(int N, int C)
- (be sure your method is public)
Constraints
- N will be between 1 and 5,000,000, inclusive.
- C will be between 1 and N, inclusive.
Examples
2
2
Returns: 8
The cat can choose any of the eight cardinal directions: horizontally, vertically, or diagonally (at 45 degrees).
2
1
Returns: 8
Again there are eight options for the cat. One of them is to run along the ray that goes approximately 26.57 degrees counter-clockwise from the positive x direction. When running along this ray the cat will catch and eat the mouse that sits on the point (2, 1), and no other mouse.
19
3
Returns: 48
One of the good options involves the cat eating the mice at (-5, 6), (-10, 12), and (-15, 18).
5000000
1
Returns: 45594542166976
1234
3
Returns: 180608
1234
1212
Returns: 0
In this setting it's not possible for the cat to catch exactly 1212 mice.
4838943
6
Returns: 419620338112
4971039
6
Returns: 442843514880
4957416
1687363
Returns: 0
4996423
1
Returns: 45529341363456
4822946
513685
Returns: 0
4969459
3
Returns: 2919209755040
4717396
5
Returns: 661406657920
4997447
83787
Returns: 0
4995036
7
Returns: 290203132272
4875562
2
Returns: 8028397074624
3805677
2394070
Returns: 0
4901105
5
Returns: 713926778944
5
5
Returns: 8
4778940
4558749
Returns: 0
4850113
7
Returns: 273610257904
1
1
Returns: 8
3
2
Returns: 0
4890231
5
Returns: 710757214768
4839329
5
Returns: 696037660464
4832558
1
Returns: 42591888256176
4824645
5
Returns: 691820179696
3
1
Returns: 24
4711646
743144
Returns: 0
4932742
3798
Returns: 0
4879261
5
Returns: 707570103616
4924237
2
Returns: 8189488383328
4947364
6
Returns: 438632587376
4931851
2
Returns: 8214835589632
4717439
5
Returns: 661414888928
4818991
6
Returns: 416167471792
4825295
7
Returns: 270816514912
4986714
4
Returns: 1360578385536
5
1
Returns: 64
4718496
2
Returns: 7519452886048
4794990
4292106
Returns: 0
4932724
1
Returns: 44375824696384
4815834
5
Returns: 689288816960
4
1
Returns: 32
4976510
3291367
Returns: 0
6
4
Returns: 0
5
4
Returns: 0
4991119
3
Returns: 2944711747664
4937812
4727873
Returns: 0
4764160
3473479
Returns: 0
2951510
262250
Returns: 0
4738716
1469040
Returns: 0
4827412
2
Returns: 7870601186016
6
1
Returns: 64
4757748
7
Returns: 263288193344
4711656
5
Returns: 659795964592
4796477
1482085
Returns: 0
5265
2162
Returns: 0
4957558
2874915
Returns: 0
4881384
3620845
Returns: 0
4858716
452087
Returns: 0
4865453
5
Returns: 703571388720
6
2
Returns: 16
4802751
2
Returns: 7790386065712
4039567
3036079
Returns: 0
4877388
391636
Returns: 0
4843214
4788516
Returns: 0
343177
219432
Returns: 0
4953727
3
Returns: 2900754915248
198483
26859
Returns: 0
4986621
1
Returns: 45350873194032
4865147
7
Returns: 275309206352
3291828
2581852
Returns: 0
4771649
2886150
Returns: 0
4756667
2238635
Returns: 0
4885310
5
Returns: 709327022832
4
2
Returns: 8
4759735
6
Returns: 405997613696
6
5
Returns: 0
5
3
Returns: 0
4885099
6
Returns: 427664978656
4898563
1033048
Returns: 0
4825366
4486968
Returns: 0
3608673
2322135
Returns: 0
4907344
3
Returns: 2846690397536
4767044
825595
Returns: 0
4721865
1178090
Returns: 0
4735213
3097489
Returns: 0
4887141
5
Returns: 709857475216
6
6
Returns: 8
4992575
2
Returns: 8418375919152
4298704
3242676
Returns: 0
4896171
6
Returns: 429602171920
3
3
Returns: 8
4710864
2216679
Returns: 0
4
4
Returns: 8
6
3
Returns: 8
4972314
7
Returns: 287568515168
4743398
1
Returns: 41034763542160
4875074
1
Returns: 43344622985984
4959362
4431498
Returns: 0
4742311
4722451
Returns: 0
4954488
3
Returns: 2901648738080
4928386
3
Returns: 2871155431184
4918449
5
Returns: 718980917504
4987234
2580893
Returns: 0
4808572
4
Returns: 1265109365360
4983182
7
Returns: 288831839360
2881243
1079731
Returns: 0
4779274
4613140
Returns: 0
4
3
Returns: 0
4946306
1666626
Returns: 0
5
2
Returns: 8
4946955
6
Returns: 438565562416
4789283
5
Returns: 681714216240
4600000
2300000
Returns: 8
4600001
2300000
Returns: 8
4599999
2300000
Returns: 0
4325643
4325643
Returns: 8
4325643
4325642
Returns: 0
5000000
2
Returns: 8443441709264
5000000
10
Returns: 105509403824