foryou1006ll   7년 전

이 문제가 code.plus 에서는 수학2 카테고리에 있던데

제가 아는 수학 지식으로는 도저히 수학처럼 보이지 않네요...!

방정식의 해의 개수를 구하는 수학 이론이 있는 것인가요?

아니면 뭔가 다른 접근법이 있는 것인가요?

너무 궁금합니다. 알려주세요!!

cozyyg   7년 전

Ax+By+C=0의 한 해 X0,Y0에 대해 X0+kB,Y0-kA 역시 해가 됩니다.
이런 식으로 하나의 해를 구하면 그 해로부터 모든 해를 일반적으로 나타낼 수 있습니다.
한 해를 구하는 것, 그리고 일반적인 해의 형태를 구하는 것 모두에서 위의 알고리즘이 쓰입니다.
이 정도면 수학이죠.

pichulia   7년 전

https://ko.wikipedia.org/wiki/...

덤으로 이런 친구도 있습니다.


foryou1006ll   7년 전

먼저 답변 감사합니다!

보내주신 링크들로 공부를 해보니 감을 좀 잡을 수 있었습니다.

확장 유클리드 알고리즘으로 해를 구한 뒤 부등식의 범위내 숫자를 카운트하는 방법으로 제출 해보았는데요!

예제와 게시판의 예시들은 모두 맞았다고 나오는데 제출하면 틀렸다고 합니다.

제가 찾지 못한 반례가 있는것 같은데.. 혹시 봐주실수 있을까요?ㅠㅠ

pichulia   7년 전

굉장히 액기스만 있는 코드네요...

몇가지 눈에 띄는게 있다면... xleft xright 구할 때 한쪽은 양수 한쪽은 음수일 경우 그 범위가 제대로 나오지 않을거같네요.

그리고 ABC가 0일 때 0을 리턴하셨는데, 이 경우에도 해는 있을 수 있습니다. 

게다가 gcd 구할 때 음수가 들어오는 경우도 생각해봐야 하고요..


괜히 숏코딩이 1.6kb인게 아닙니다

foryou1006ll   7년 전

gcd 구할 때 음수인 경우도 신경써 봤구요...

ABC각각이 0인 경우들에 대해서도 신경써 봤는데... 여전히 틀렸다고 하네요 ㅠㅠㅠ

xleft, xright는 밑에서 xmin, xmax를 다시 구하기 때문에 부호와 상관없이 범위가 나온다고 생각했습니다!

혹시 이부분에 오류가 있을까요?

foryou1006ll   7년 전

답변 해주신 분들 모두 감사합니다!

반례를 찾아서 드디어 풀었습니다!

foryou1006ll   7년 전

소스 코드를 지울까 하다가...

저 처럼 고생하실 분들이 감이라도 잡고 가시라고 그대로 남겨 두겠습니다!!

예제는 통과하고 반례는 찾기 힘든 생각의 힘을 기를 수 있는 아주 좋은 코드라고 생각... 합니다!

sait2000   7년 전

반례 만들어오니까 질문글이 지워져있어요 어머나 세상에

sait2000   7년 전

input: 2 9 3 3 5 -6 9 output: 1 이런 거 만들었는데 ㅠㅠ

foryou1006ll   7년 전

sait2000님 ㅋㅋㅋ

sait2000님이 새롭게 맞은사람으로 등록되신거 보고 와 부럽다... 하다가 마침 풀렸는데!!

반례까지 챙겨주시다니ㅠㅠ

찾아주신 반례는 이 글에 달아서 다른 분들에게 분명 많은 도움이 될것 입니다!

감사합니다!!

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