TopCoder problem "Apportionment" used in TCHS SRM 23 (Division I Level Two)



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

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6740

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10075&pm=6740

Writer:

VitalyGoldstein

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Math