지진

시간 제한1초메모리 제한128 MB

요약

양의 정수 A, B, C가 주어질 때 x≥0, y≥0이고 Ax+By≤C인 정수 격자점의 개수를 센다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 기하
정답자: 아직 제출이 없습니다

문제

무한 도시(Infinity City)는 무한한 사분면 위에 자리 잡고 있습니다. 정수 좌표 $x \ge 0$ , $y \ge 0$ 인 모든 점 $(x, y)$ 마다 고층 빌딩이 정확히 하나씩 서 있으므로, 도시에는 빌딩이 무한히 많습니다.

어느 날 지진이 일어나 직선 $Ax + By = C$ 를 따라 거대한 균열이 생겼습니다. $Ax + By > C$ 를 만족하는 점에 있던 빌딩은 모두 무너져 사라졌고, $Ax + By \le C$ 를 만족하는 빌딩만 남았습니다. 이제 도시는 유한해졌습니다. 남아 있는 빌딩은 모두 몇 개일까요?

입력

한 줄에 세 개의 양의 정수 $A$ , $B$ , $C$ 가 공백으로 구분되어 주어집니다. $1 \le A, B \le 10^9$ 이고 $1 \le C \le \min(A, B) \times 10^9$ 입니다.

출력

남아 있는 빌딩의 개수를 정수 하나로 출력합니다.

예제3

예제 1
입력
```
3 4 13
```
예상 출력
```
12
```
예제 2
입력
```
1 1 1
```
예상 출력
```
3
```
예제 3
입력
```
2 3 6
```
예상 출력
```
7
```