/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
2 次元平面上に (0,0), (W,0), (0,H), (W,H) を頂点とするような長方形 R があります。 W, H は正の整数です。 このとき、次の条件をすべて満たすような 2 次元平面上の三角形 \Delta の個数を求めてください。
- \Delta の各頂点は格子点である。つまり、座標がいずれも整数である。
- \Delta と R は頂点を共有しない。
- \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