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 long
Method signature:long long howMany(int width, int height)
CONSTRAINTS
-width and height will each be between 1 and 10^5, inclusive.
EXAMPLES
0)
1
1
Returns: 1
There is only one square.
1)
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).
2)
3
3
Returns: 20
3)
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)2010, TopCoder, Inc. All rights reserved.