Apportionment | Topcoder Archive

Problem Statement

A square is divided into N * M equal rectangles.
For example, here's a square divided into 2 * 3 rectangles:
+--+--+--+ |**|**|**| |**|**|**| |**|**|**| +--+--+--+ |**|**|**| |**|**|**| |**|**|**| +--+--+--+ Find the number of squares made up by these rectangles, i.e., all vertices of squares must coincide with one of the rectangles' vertices. You should count only squares with non-zero area. Two squares are equal if and only if they share the exact same set of vertices. Only count squares whose sides are parallel to the sides of the original square.

Definition

Class:: Apportionment
Method:: numberOfSquares
Parameters:: int, int
Returns:: long
Method signature:: long numberOfSquares(int N, int M)
(be sure your method is public)

Constraints

N and M will each be between 1 and 100000, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 1
```
Here there is only square.
```
2
```
```
2
```
```
Returns: 5
```
Here there are 4 smaller squares (each of the rectangles is a square), along with the one original square.
```
2
```
```
3
```
```
Returns: 1
```
```
6
```
```
4
```
```
Returns: 13
```
```
76711
```
```
54969
```
```
Returns: 1
```

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.