devil7269   1년 전

유클리드의 뭐시기 이런거는 잘 모르고, 그냥 수학푼다는 느낌으로 풀었는데 대충 답은 거의 다 맞는거같은데 틀렸습니다가 뜹니다 ㅠㅠ. 반례알려주시면 감사하겠습니다!

kjk9704   1년 전

약분을 담당하는 조건문에서 잘못되었습니다.

input

1 4

1 8

output

12 32

answer

3 8

12 % 32는 0이 아니면서 동시에 32 % 12는 0이 아니라서 약분 자체를 하지 못 해 반례가 발생합니다.

유클리드 호제법은 앞으로 나올 악랄한 정수론 공식들에 비해 정말 쉬운 편입니다.

조건문 대신 유클리드 호제법을 Java로 구현해서 최대공약수를 구하고 기약분수 형태로 구하면 AC 판정 받을 수 있습니다.

여기를 참고해주세요.

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