分数: 1000 点
问题陈述
在二维平面中,我们有一个矩形 R 其顶点是 (0,0), (W,0), (0,H),和 (W,H),其中 W 和 H 是正整数。 在这里,找到三角形的数量 \Delta 在满足以下所有条件的飞机上:
- 每个顶点 \Delta 是一个网格点,即有整数 x- 和 y- 坐标。
- \Delta 和 R 不共享顶点。
- 每个顶点 \Delta 位于 R,并且所有顶点都属于不同的边 R.
- \Delta 最多包含 K 网格点严格位于其自身内部(不包括其周长和顶点)。
约束
- 1 \leq W \leq 10^5
- 1 \leq H \leq 10^5
- 0 \leq K \leq 10^5
输入
输入由标准输入按以下格式给出:
W H K
输出
打印答案。
示例输入 1
2 3 1
示例输出 1
12
例如,具有顶点的三角形 (1,0), (0,2),和 (2,2) 自身仅包含一个网格点,因此满足条件。
示例输入 2
5 4 5
示例输出 2
132
示例输入 3
100 100 1000
示例输出 3
461316