Odd Area Lattice Squares
Time limit5sMemory limit256 MB
You count every lattice square with odd area that fits inside each m by n grid.
- Level
Medium7 of 10
- Topics
- Combinatorics, Math, Geometry
- Solved
- No attempts yet
Problem
A lattice square is a square whose four vertices all lie on lattice points. A lattice point is a point whose coordinate and coordinate are both integers. For example, is a lattice point and is not.
An grid is cells wide and cells tall. Its lattice points are the integer points with and .
Some lattice squares that fit in the grid have sides parallel to the axes, and others are tilted. If one side of a lattice square is the vector , the square has area , so a tilted square also has an integer area. The square built on has area , which is odd, and the square built on has area , which is even.
Given the size of the grid, count the lattice squares that fit in the grid and have odd area.
Two lattice squares are different unless they share all four sides.
Input
The input has at most 50000 lines. Each line contains two integers and , the size of the grid ().
The last line contains two zeros. That line is not processed.
Output
For each grid, print the number of lattice squares with odd area, one per line. The answer always fits in a 64-bit signed integer.