gs25   5년 전

풀이는 a*x + b*y = n ( gcd(x,y)=1) 인 경우를 찾아야하니 가능한 x 중 최소 x를 잡고 ( b 보다 미만 0이상) x + b, y -a 를 계속 반복해주며 y가 0이상인 범위에서 gcd 값이 1인지를 체크해줬습니다. 풀이에 대한 정당성은 이 글을 참고했습니다. https://rkm0959.tistory.com/96

 구현은 오버플로우때문에 __int128로 모두 처리해줬습니다. 입력에서 a.b 가 10^18 보다 작으므로 __int128에서는 오버플로우가 안날 것 같이고 실제로 assert 부분도 통과를 했습니다. a 또는 b 또는 s 가 0인 경우도 모두 예외처리해줬습니다. 어디가 틀렸는지 반례가 있는지 모르겠습니다...

amel   5년 전

55번 줄에 "No"가 아니라 "NO" 아닌가요?

gs25   5년 전

앗 그렇습니다

gs25   5년 전

어머 저희학과 선배님이시네요 ! 반갑습니다 

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