Counting Lattice Points Inside a Triangular Electric Net

Farmer John builds an electric triangular net to enclose his cows. The triangle is formed by connecting three lattice points (points with integral coordinates): the origin (0,0), the point (n, m) with 0 ≤ n < 32000 and 0 < m < 32000, and the point (p, 0) with p > 0. The triangle is constructed by connecting these points in order: starting at the origin, connecting to (n, m), then to (p, 0), and finally returning to the origin.

The cows can be placed on any lattice point strictly inside the triangle (i.e. not on its boundary). Determine how many cows can be placed inside the electric net.

This problem can be solved using Pick's Theorem. Pick's Theorem states that for a lattice polygon,

$$A = I + \frac{B}{2} - 1,$$

where:

• A is the area of the polygon,
• I is the number of lattice points strictly inside the polygon, and
• B is the number of lattice points on the boundary.

For this triangle, the area is:

$$A = \frac{p \times m}{2}.$$

The number of lattice points on each edge is as follows:

• Edge from (0,0) to (n, m): gcd(n, m) + 1
• Edge from (n, m) to (p, 0): gcd(|p-n|, m) + 1
• Edge from (p, 0) to (0,0): p + 1 (since all points are of the form (i, 0), 0 ≤ i ≤ p)

Since the vertices are counted in two edges, the total number of boundary points is:

$$B = \gcd(n,m) + \gcd(|p-n|, m) + p.$$

Rearranging Pick's Theorem, the number of interior lattice points I is:

$$I = A - \frac{B}{2} + 1 = \frac{p\times m - (p + \gcd(n,m) + \gcd(|p-n|, m)) + 2}{2}. $$

Your task is to compute I for the input triangle.

inputFormat

The input consists of a single line containing three space-separated integers:

1. n (with 0 ≤ n < 32000),
2. m (with 0 < m < 32000),
3. p (with p > 0).

outputFormat

Output a single integer, the number of lattice points strictly inside the triangle.

sample

1 1 1

0