17467번 - N! mod P (2)
Barrett Reduction을 사용해 2684ms로 통과했습니다. 조언 감사드립니다. 루프 언롤링이나 분기 제거는 채점 환경에서는 어떨지 모르겠습니다만 로컬에서는 성능 향상이 없더군요.
참고로 파이썬에서는 윌슨의 정리만 사용해도 가능합니다.
정말 그렇네요. 이게 왜 되는 거지..
@not_stober 파이썬은 애초에 큰자리수 연산이 기본적으로 지원합니다.
@jwoo101010 물론 그렇습니다만, 이 경우는 모듈로 연산의 속도 문제이니 PyPy의 JIT 컴파일러가 최적화를 잘하는 것으로 보이네요.
댓글을 작성하려면 로그인해야 합니다.
not_strober 1년 전
코드와 같이 풀었습니다. for 루프의 반복 횟수가 약 5x108이라 3초 제한에 들어갈 것 같았는데 안 되더군요.
FFT를 사용해 푸는 문제는 https://www.acmicpc.net/proble... 여기 따로 있던데, 윌슨의 정리만 쓰는 현재 코드에서는 코드를 최적화할 부분이 보이지가 않습니다. 접근 방법이 틀린 건지도 모르겠네요. 혹시 윌슨의 정리를 사용하면서 FFT 없이 푸신 분 있으면 조언 부탁드립니다.