F - Triangles /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1000

問題文

2 次元平面上に (0,0), (W,0), (0,H), (W,H) を頂点とするような長方形 R があります。 W, H は正の整数です。 このとき、次の条件をすべて満たすような 2 次元平面上の三角形 \Delta の個数を求めてください。

  • \Delta の各頂点は格子点である。つまり、座標がいずれも整数である。
  • \DeltaR は頂点を共有しない。
  • \Delta の各頂点は R の周上にあり、それぞれが属する辺は相異なる。
  • \Delta の内部(周上及び頂点を含まない)にある格子点は高々 K 個である。

制約

  • 1 \leqq W \leqq 10^5
  • 1 \leqq H \leqq 10^5
  • 0 \leqq K \leqq 10^5
  • 入力で与えられる値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

W H K

出力

答えを出力せよ。


入力例 1

2 3 1

出力例 1

12

例えば (1,0), (0,2), (2,2) を頂点とするような三角形は、 内部に格子点が 1 つしか存在しないので、条件を満たします。


入力例 2

5 4 5

出力例 2

132

入力例 3

100 100 1000

出力例 3

461316

Score : 1000 points

Problem Statement

In a two-dimensional plane, we have a rectangle R whose vertices are (0,0), (W,0), (0,H), and (W,H), where W and H are positive integers. Here, find the number of triangles \Delta in the plane that satisfy all of the following conditions:

  • Each vertex of \Delta is a grid point, that is, has integer x- and y-coordinates.
  • \Delta and R shares no vertex.
  • Each vertex of \Delta lies on the perimeter of R, and all the vertices belong to different sides of R.
  • \Delta contains at most K grid points strictly within itself (excluding its perimeter and vertices).

Constraints

  • 1 \leq W \leq 10^5
  • 1 \leq H \leq 10^5
  • 0 \leq K \leq 10^5

Input

Input is given from Standard Input in the following format:

W H K

Output

Print the answer.


Sample Input 1

2 3 1

Sample Output 1

12

For example, the triangle with the vertices (1,0), (0,2), and (2,2) contains just one grid point within itself and thus satisfies the condition.


Sample Input 2

5 4 5

Sample Output 2

132

Sample Input 3

100 100 1000

Sample Output 3

461316