yclock   9달 전

KOI 공식 만점 소스는 특정 바퀴의 회전 속도를 다음과 같이 구합니다.

speed = (speed / a) * b;

이는 입력으로 주어지는 a, b가 gcd(a, b) = 1를 항상 만족한다는 가정 하에 성립하는 식입니다.

만일, 입력을 다음과 같이 주면, 문제에서 입력에 관한 조건(a, b는 양의 정수, 모든 바퀴의 회전수는 10^9 이하의 양의 정수)을 모두 만족합니다.

2

1 999999999 0

1000000000 1000000000 0


이 때의 바퀴 회전수는 {1, 999999999, 999999999} 이며 문제의 조건을 모두 만족함을 알 수 있습니다.

그러나 공식 소스에 대입할 시, speed / a를 계산하는 과정에서 일어나는 'int 나눗셈 특성' 때문에, 답이 나오지 않음을 알 수 있습니다.


따라서, 입력으로 주어지는 a, b에 대해, 항상 gcd(a, b) = 1를 만족한다는 조건을 추가해 주셨으면 감사하겠습니다. (이제는 공식 소스도 저격하고 있는 나를 발견하였다..!)

댓글을 작성하려면 로그인해야 합니다.