SquaresInsideLattice | Topcoder Archive

Problem Statement

We define a rectangular lattice as the set of all points with integer coordinates (x,y) such that 0 <= x <= width and 0 <= y <= height. A square is inside this lattice if and only if all its vertices belong to the lattice. Two squares are different if there exists at least one point which is a vertex of the first square but not a vertex of the second square. The edges of a square are not required to be parallel to the axes. Return the number of different squares inside the lattice.

Definition

Class:: SquaresInsideLattice
Method:: howMany
Parameters:: int, int
Returns:: long
Method signature:: long howMany(int width, int height)
(be sure your method is public)

Constraints

width and height will each be between 1 and 10^5, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 1
```
There is only one square.
```
2
```
```
3
```
```
Returns: 10
```
There are 6 squares with area 1, 2 squares with area 4, and 2 squares with area 2 (their sides are not parallel to the axes).
```
3
```
```
3
```
```
Returns: 20
```
```
27
```
```
19
```
```
Returns: 23940
```

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.