풀이는 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인 경우도 모두 예외처리해줬습니다. 어디가 틀렸는지 반례가 있는지 모르겠습니다...
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인 경우도 모두 예외처리해줬습니다. 어디가 틀렸는지 반례가 있는지 모르겠습니다...