시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 189 | 137 | 128 | 81.013% |
Albert는 개구리 장난감을 이용한 놀이를 즐겨한다. 이 장난감은 우측으로 $A$cm 혹은 좌측으로 $B$cm 점프할 수 있다.
예를 들어 현재 개구리 장난감의 위치가 $0$이고 $A = 4$, $B = 2$ 라 하자. 아래 그림에서 음수는 처음 위치에서 좌측을, 양수는 우측을 나타내며 거리의 단위는 cm (centimeter) 이다.
만약 개구리가 우측으로 점프를 한 번 한다면, 아래 그림처럼 $4$cm 만큼 이동한 위치에 착지하게 된다.
이후 좌측으로 한 번 점프하면 $2$cm 만큼 이동한 위치에 착지한다.
여기서 다시 좌측으로 두 번 더 점프하면 총 $4$cm를 움직이게 되어 처음 위치에서 좌측으로 $2$cm 떨어진 지점에 착지한다.
위 예제의 경우 개구리가 무한정 점프할 수 있더라도 처음 위치에서 $1$cm 떨어진 곳에 도달할 수 있는 방법은 없다. 이를 깨달은 Albert는 문득 궁금해졌다 -- 개구리가 무한정 점프할 수 있을 때, 처음 위치에서 우측으로 $1$cm, $2$cm, $\dots$, $X$cm 떨어진 (총 $X$개의) 위치들 중 몇 곳에 도달할 수 있을까? 위 예제의 경우 $A = 4$, $B = 2$ 라면 $X = 10$ 일 때 처음 위치에서 우측으로 $2$cm, $4$cm, $6$cm, $8$cm, $10$cm 위치에 도달할 수 있으므로 정답은 $5$가 된다.
Albert를 도와 $A$, $B$, $X$가 주어졌을 때 답을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스는 한 줄에 세 개의 정수 $A$, $B$, $X$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
7 4 2 10 2 4 11 5 3 15 20 22 2022 6 9 2000000000 1 1 2000000000 4 7 2
5 5 15 1011 666666666 2000000000 2
예제 1: 본문에서 다루었다.
예제 2: 예제 1과 비슷하게 $2$cm, $4$cm, $6$cm, $8$cm, $10$cm 지점에 도달할 수 있으므로 정답은 $5$가 된다.
예제 3: 이 경우 $1$cm, $2$cm, $\dots$, $15$cm 지점에 모두 도달할 수 있다. 예를 들어 $7$cm 지점에 도달하는 방법 중 한 가지는 우측으로 두 번 ($+10$cm) 점프 한 후 좌측으로 한 번 ($-3$cm) 점프하면 된다.
예제 6: 모든 지점에 도달 가능하다.
예제 7: $1$cm 지점에 도달하기 위해 우측으로 두 번, 좌측으로 한 번 점프하면 된다. $2$cm 지점에 도달하기 위해 좌측으로 두 번, 우측으로 네 번 점프하면 된다. 이 외에도 다양한 방법으로 $1$cm나 $2$cm지점에 도달할 수 있다.