홀수인경우 처리방식에 궁금점이 있습니다

작성한 질문수 8

0

안녕하세요 수현님 ㅎㅎ

모듈러 연산의 특징은 앞의 그림과 같습니다.

(ret * a%c) % c

>> 이렇게 하셔도 되긴 합니다. 사실 수현님의 방법이 좀 더 안전한 방법입니다. a가 매우 큰 수일 때는 c로 먼저 모듈러 연산을 적용하는게 좋습니다.

하지만 이 문제에서 a는 int의 최대값이며 제곱했을 때 long long을 초과하지 않는 범위기 때문에 저 연산은 필요가 없으며(ret * a) % c 이렇게 해도 어차피 모듈러 공식에 의해 안에 다 모듈러가 적용이 되기 때문에 그렇게 안하셔도 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

안녕하세요, 인프런 AI 인턴입니다.

전수현님의 질문과 유사한 상황에 대한 설명을 제공하는 내용이 있어서 안내해드리겠습니다.

홀수일 때의 처리 방식, 특히 모듈러 연산에서 (ret * a) % c와 (ret * a%c) % c의 차이에 대해 궁금증을 가진 경우와 관련해, 큰돌 강사님께서 제공한 설명을 참조하실 수 있습니다.

• 질문: 홀수일 경우의 처리 방식에 대한 이해가 어려울 때, 특히 (ret * a) % c 사용의 타당성에 대한 질문입니다.
  

해당 질문과 가장 잘 맞는 설명은 “선생님 홀수인 경우가 살짝 이해가 안됩니다.”에서 제공되었습니다. 이 답변에서 큰돌 강사님은 모듈러 연산에서의 처리 방식, 특히 if (b % 2) ret = (ret * a) % c; 부분의 사용 이유와 그 타당성을 설명하고 있습니다.

요약하자면, 강사님이 제시한 (ret * a) % c 계산 방식은 올바른 모듈러 연산 처리 방식입니다. (ret * a%c) % c로 계산하셔도 궁극적으로는 같은 결과가 나오지만, a%c를 하게 되면 불필요한 모듈러 연산이 추가되므로, 이미 ret % c가 적용되어 c보다 작은 상태라면 a에 대해서만 % c를 해도 충분히 올바른 결과를 보장합니다. 이는 효율적인 코드 작성을 위한 한 방법으로 볼 수 있습니다.

이에 대해 더 자세한 설명을 원하신다면, 위 링크를 참조해 주시면 좋을 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.