CatAndMice | Topcoder Archive

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).
```
1234
```
```
3
```
```
Returns: 180608
```
```
1234
```
```
1212
```
```
Returns: 0
```
In this setting it's not possible for the cat to catch exactly 1212 mice.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.