Codeforces Round 865 (Div. 2) - A. Ian Visits Mary (800)
문제의 조건을 잘 읽어보면 $(0, 0)$ 부터 시작하고 $1 \le a,b$ 이고 동일한 위치를 두 번 출력해도 된다고 한다.
$gcd(x,y)=1$ 여야 하는 위치로만 갈 수 있는데, 그럼 $x=1$ 이나 $y=1$ 이면 항상 가능하다는 것을 의미한다.
따라서 $(1,b-1)$ 로 먼저 간다.
이제 $(a-1, 1)$ 만큼 움직일 수 있으므로 두 번의 이동 모두 $gcd(x,y)=1$ 이므로 항상 가능하다.
$a-1$이나 $b-1$ 은 $0$ 이상이고 문제의 조건에서 $0 \le x_i, y_i \le 10^9$ 라고 했으므로 이렇게 풀라고 낸 문제임을 알 수 있다.
Comments