kimsy96   2년 전

거의 소수라는 조건 때문에 전체제한의 루트값(10^7) 까지만 에라토스테네스의 체를 이용해서 처리한다음 풀어야 한다는 거 까지는 잡았습니다.

구해놓은 소수에 대하여 구간 a,b안에 들어가는 거의소수를 구하는 과정에서 오버플로우를 방지하는게 문제의 핵심인거 같은데..

제 나름대로 시도를 해봤지만 실패했습니다.

논리적으로 조금 엉성하다고 생각은 하지만

if(next/now!=i) break; 요 부분에서 만약오버플로우가 발생했다면 값이 뒤틀려서 저 조건식을 만족하지 못할 것이라고 생각했습니다. 

조금 도와주셨으면 합니다 

kimsy96   2년 전

....?

next/now!=i 요 부분을

next%now!=0 으로 고치니까 맞네요.. ;

저렇게 캐치하면 안되는 이유는 뭘까요 

kimsy96   2년 전

제풀이를 저도 잘 모르겠네요

next%now!=0 이걸로 오버플로우가 잡힌다고 생각했는데.. 안잡힐수도 있지않나요?

kimsy96   2년 전

요게 ac받은 소스코드...

질문을 요약하자면

첫번째 WA받은 풀이의 오버플로우 판별  next/now!=i  이 안되는 이유(이건 어렴풋이 알듯합니다 그래도 갓갓분들의 명쾌한 설명이 듣고싶습니다)

두번째 AC받은 밑의 풀이의 오버플로우 판별법 if(next%now!=0) break; 오버플로우되서 값이 어디로 튀느냐에 따라 저걸로 판별못하는 상황이 발생하지않을까요? 

hayman42   2년 전

혹시 next / now != i 가 안되는 이유를 어렴풋이라도 알려주실 수 있을까요?

저도 초보자라서 왜 안되는지는 잘 모르겠지만 % 가 되는 이유는 단순히 정말 절묘하게 next 가 오버플로우가 일어나면서 now 의 배수가 되는 데이터가 없기 때문 아닐까요?

kimsy96   2년 전

음.. 어렴풋이 이해했다고 생각했는데 아니었어요 여전히 모르겠네요 ㅋㅋㅋㅋ

저소스코드 돌려보면 40퍼센트 정도에서 틀렸다고 나오는데 반례도 못찾겠네요 음

kimsy96   2년 전

오버플로우가 발생해서 값이 음수로 튀니까 몫이 음수가 되어 저렇게 판별할 수 있을거라 생각했는데 ..

kimsy96   2년 전

몇몇 실력좋은 분들과 이야기 해본 결과

약간의 운이 작용했다..라는 결론을 얻었고

풀이는 참고만 하시고

오버플로우는 다른방식으로 처리하시길 권장합니다 

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