인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

이부분을 한꺼번에 하려고 하니 오버플로가 나는 것 같습니다.

	if (div % 2){
		return ((temp % c) * (temp % c) * (n % c)) % c;

예를 들어 c가 3이고 저 숫자들이 2라고 했을 때

2곱하기 2를 3으로 모듈러 하는거랑 2곱하기 2 곱하기 2를 3으로 모듈러 연산하는 것을 생각하시면 됩니다.

제가 다듬은 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll a, b, c;

ll recur(ll n, ll div) {
    if (div == 1) {
        return n % c;
    }
    ll temp = recur(n, div / 2);
    temp = (temp * temp) % c;
    if (div % 2) {
        return (temp * n) % c;
    } else {
        return temp;
    }
}

int main() {
    cin >> a >> b >> c;
    cout << recur(a, b) << endl;
    return 0;
}

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

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

감사합니다.

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

민우 님의 질문과 관련하여, 1-N: 1629 곱셈 문제 에 대한 이전 질문 중 하나에 제공된 답변이 유용할 것으로 보입니다. 해당 문제에 대해 고민 중이신 것으로 보이는 코드 문제에 대한 해결 방법을 찾으실 수 있을 것입니다.

큰돌 강사님께서 제공하신 답변은 문제 코드에서 % 연산이 누락되었을 가능성에 대한 지적을 포함하고 있습니다. 구체적으로는, 코드 내에서 중간 결과값에 대한 모듈러 연산을 수행해야 한다는 조언을 제공하고 있습니다.

이와 관련된 질문 및 답변 링크는 다음과 같습니다:

• “1-N: 1629 곱셈 문제 질문 드립니다.”에 대한 답변에서, % 연산을 해야 되지 않을까요? 라는 조언이 있었습니다.
  

이 조언은 민우 님께서 직면하신 문제와 유사할 수 있기에, 코드 내부에서 모든 중간 곱셈 연산 이후에 모듈러 연산을 적용했는지 확인해보시는 것이 좋을 것 같습니다. 특히, 대규모 수를 다룰 때는 중간 결과값도 모듈러 연산을 적용해야 오버플로를 방지하고 정확한 결과를 얻을 수 있습니다.

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