A. Ian Visits Mary

문제의 조건을 잘 읽어보면 (0,0)(0, 0) 부터 시작하고 1≤a,b1 \le a,b 이고 동일한 위치를 두 번 출력해도 된다고 한다.

gcd(x,y)=1gcd(x,y)=1 여야 하는 위치로만 갈 수 있는데, 그럼 x=1x=1 이나 y=1y=1 이면 항상 가능하다는 것을 의미한다.

따라서 (1,b−1)(1,b-1) 로 먼저 간다.

이제 (a−1,1)(a-1, 1) 만큼 움직일 수 있으므로 두 번의 이동 모두 gcd(x,y)=1gcd(x,y)=1 이므로 항상 가능하다.

a−1a-1이나 b−1b-1 은 00 이상이고 문제의 조건에서 0≤xi,yi≤1090 \le x_i, y_i \le 10^9 라고 했으므로 이렇게 풀라고 낸 문제임을 알 수 있다.

Comments

You may also enjoy