Counting Triangles
Time limit2sMemory limit512 MB
Count the lattice triangles with nonzero area whose three vertices lie on the grid points of an M by N rectangle, for up to 21 cases.
- Level
Medium7 of 10
- Topics
- Combinatorics, Math, Number theory, Geometry
- Solved
- No attempts yet
Problem
A triangle is a polygon with three sides and strictly positive area. A lattice triangle is a triangle whose vertices all have integer coordinates. In this problem you have to find the number of lattice triangles in an M × N grid. For example, a 1 × 2 grid contains 18 different lattice triangles, as shown in the picture below.
Figure 2: Lattice triangles in a 1 × 2 grid
Input
The input file contains at most 21 test cases.
Each test case consists of a line with two integers M and N (0 < M, N ≤ 1000). These two integers mean that you have to count triangles in an M × N grid.
The input is terminated by a case where both M and N are zero. This case is not processed.
Output
For each test case, print one line. This line contains the case number followed by the number of lattice triangles in the grid. You can assume that the number of triangles fits in a 64-bit signed integer.