LotsOfLines | Topcoder Archive

Problem Statement

Note that the memory limit for all tasks in this SRM is 256 MB.

You are given ints A and B. These determine a set of A*B lines in the plane: for each pair of integers (a,b) such that 0 <= a < A and 0 <= b < B, there is a line with the equation y=ax+b.

These lines divide the plane into several regions. (Some of them are finite, some are infinite.) Compute and return the total number of regions.

Definition

Class:: LotsOfLines
Method:: countDivisions
Parameters:: int, int
Returns:: long
Method signature:: long countDivisions(int A, int B)
(be sure your method is public)

Notes

Formally, the line with the equation y=ax+b is the set of all points (x,y) such that x is any real number and y=ax+b.

Constraints

A will be between 1 and 1,200, inclusive.
B will be between 1 and 1,200, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 2
```
There is only one line: y=0. This line divides the plane into two regions.
```
2
```
```
2
```
```
Returns: 9
```
There are four lines. The plane looks as follows.
```
3
```
```
2
```
```
Returns: 17
```
```
1
```
```
1200
```
```
Returns: 1201
```
There are 1,200 horizontal lines.
```
5
```
```
9
```
```
Returns: 638
```

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.