← 返回题目列表

AtCoder · tokiomarine2020_f

F. 三角形

中文机器翻译题面 查看原题

分数: 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