메모리: 14372 KB, 시간: 176 ms
브루트포스 알고리즘, 유클리드 호제법, 수학, 정수론
2024년 1월 8일 13:26:21
2차원 좌표 평면 위에서 두 점을 골라 선분을 그었을 때, 지나가는 점의 개수가 K개인 선분의 수를 구해보자.
가능한 점의 좌표 (x, y)는 0 ≤ x ≤ N, 0 ≤ y ≤ M 이고, x와 y는 정수이다. 선분의 양 끝점도 선분이 지나가는 점이다.
첫째 줄에 N, M, K가 주어진다.
첫째 줄에 지나가는 점의 개수가 K개인 선분의 수를 출력한다.