정수 좌표의 개수
시간 제한2초메모리 제한512 MB
격자 위에서 두 점을 이은 선분이 정확히 K개의 격자점을 지나도록 하는 점 쌍의 수를 구한다.
문제
2차원 좌표 평면 위에서 두 점을 골라 선분을 그었을 때, 지나가는 점의 개수가 K개인 선분의 수를 구해보자.
가능한 점의 좌표 (x, y)는 0 ≤ x ≤ N, 0 ≤ y ≤ M 이고, x와 y는 정수이다. 선분의 양 끝점도 선분이 지나가는 점이다.
입력
첫째 줄에 N, M, K가 주어진다.
출력
첫째 줄에 지나가는 점의 개수가 K개인 선분의 수를 출력한다.
제한
- 1 ≤ N, M ≤ 50
- 2 ≤ K ≤ 50