확장 유클리드 알고리즘 이용해서 풀어봤는데요.

아마 고민 시간이 개월 단위로 늘어나겠지만 현재 한 다섯시간째 디버깅하고 있는데

이쯤되면 다 찾았다 싶었는데도 계속 틀렸습니다가 뜹니다.

아 그리고 혹시 이거 틀리고 질문 검색하실 분들을 위해서 제가 디버깅하면서 찾은 놓친 점들을 몇개 말해드리겠습니다.

주의해야할 점 정리

1. A = 0, B = 0, C = 0 인 경우를 제외하고는 int 로만 해결된다고 생각할 수 있는데,
int 와 int 끼리의 곱셈이 확장 유클리드 알고리즘에서 사용될 수 있기 때문에 데이터 타입은 long long 으로

2. C++에서 -9를 -4로 나누면 몫이 -2, 나머지가 -1로 나옴. 음수 나눗셈과 양수 나눗셈이 다름.

3<= 2k <= 5와 -3 <= 2k <= -2 에서 전자는 2<=k가 되지만, 후자는 -1<=k가 됨. 정수 나눗셈은 부호에 따라서 다르게 해주는게 필요.

이걸 피하기 위해서 double형으로 나눈 다음 ceil과 floor를 사용할 수도 있는데 저의 경우는 좀 더 신속하게 틀렸습니다가 뜨더군요.

3. A와 B 둘 중 하나만 0일 경우엔 Ax = C 가 되서 답이 한개라고 생각하면 안 됨. B가 0이라서 y는 모든 숫자가 다 된다는 걸 생각해야하고
Ax = C를 만족하는 정수해 x가 존재하지 않을 수도 있음.

그리고 혹시 푸신 분들 아 저 인간 너무 딱하다 반례는 찾기 귀찮은데 소스 정돈 보내줄 수 있다 생각하시는 분들

kinssang@gmail.com으로 메일 보내주시면 감사하겠습니다.