글 읽기 - Miller 소수 추측에서 {2, 7, 61} 로 2*10^12 까지 성립?

dh0450 1년 전 0

https://www.acmicpc.net/source...

에서 2, 7, 61 을 쓰는데 https://en.wikipedia.org/wiki/... 를 보면 이 수로는 4,759,123,141 까지 성립한다고 나와있습니다.

그런데 인풋은 2*10^12 의 범위인데, 이렇게 넣어도 통과가 되네요.

그냥 테스트케이스가 약할걸까요? 아니면 다른 이유가 있는걸까요?

ghkoh_97 1년 전 0

저도 궁금합니다. 저는 심지어 2, 7, 61은 성공했는데 341,550,071,728,321까지 성립하는 2, 3, 5, 11, 13, 17을 넣었을 때에는 100%에서 틀렸다고 나오더라구요. c++의 경우에는 유클리드 체로 통과한 케이스가 있는 것으로 보아 테스트케이스가 잘못된 것 같지는 않은데 왜그럴까요?

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

문제

문제

출처

ICPC

Miller 소수 추측에서 {2, 7, 61} 로 2*10^12 까지 성립?

dh0450 1년 전 0

ghkoh_97 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말