완료됨
crt 관련

73, 83, 89, 97, 103, 79, 101, 127, 131, 137에서 137을 제외한 나머지 수들의 공배수를 구하는게 핵심인데, mod 결과가 모두 0이어야(공배수) 하는 조건인데 CRT를 쓰는 이유가 있나요?

다른 풀이 보다가 궁금해서 물어봅니다

#reversing
작성자 정보
더 깊이 있는 답변이 필요할 때
드림핵 팀과 멘토에게 직접 문의해 보세요!
답변 1
avatar
mini_chip
대표 업적 없음
avatar
mini_chip
대표 업적 없음

안녕하세요, 말씀 주신대로 mod 결과가 0이 되게 만든다면 해당 슬롯은 값이 바뀌지 않는데요. 이를 이용하여 7이 나올 때 까지 돌린 후 7이 나온 이후 해당 슬롯의 공배수만큼 돌려 다른 슬롯들이 7이 나올 때 까지 돌리는 전략을 사용할 수 있습니다.

다만, CRT를 사용하면 임의의 값 a에 대해 mod a가 되도록 하는 값을 구할 수 있습니다. 슬롯에 적용하면, 돌렸을 때 a만큼 이동하는 효과를 얻을 수 있다는 의미인데요. 현재 슬롯의 값 기준으로 7이 떨어진 위치를 각 슬롯별로 S0, S1, S2, ... 라 하면, 이를 기준으로 CRT를 계산하면 한 번에 잭팟을 터뜨릴 수 있는 슬롯 회전 수를 구할 수 있게 됩니다.

말씀 주신 공배수를 구하는 것도 유효하나, CRT는 또 다른 유효한 전략이라고 정리할 수 있을 것 같습니다.
감사합니다.

2025.09.08. 16:05