P2735 [USACO3.4] Electric Fences

In this problem, a lattice point is a point whose $x$ and $y$ coordinates are both integers. To pen his cows, Farmer John builds a triangular electric fence. He runs a live wire from the origin $(0,0)$ to the lattice point $(n,m)$ ($0 \le n < 32000, 0 < m < 32000$), then to the lattice point $(p,0)$ ($p > 0$), and finally back to the origin. Cows can be placed at every lattice point strictly inside the fence without touching the fence (very skinny cows). If a lattice point touches the fence, a cow absolutely cannot be placed there (perhaps Farmer John would get a little shock). How many cows can be placed inside Farmer John’s electric fence?

The input contains a single line with three integers separated by spaces: $n, m, p$.

Output a single line containing one integer, the number of cows that can be enclosed by the specified electric fence.

Problem translation is from NOCOW. USACO Training Section 3.4. Translated by ChatGPT 5