재귀함수 질문있습니다.

작성한 질문수 192

0

안녕하세요 ekek님 ㅎㅎ

1 - N 곱셈문제입니다.

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b){
    if(b == 1) return a % c;
    ll ret = go(a, b / 2);
    ret = (ret * ret) % c;
    if(b % 2)ret = (ret * a)% c;
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a >> b >> c;
    cout << go(a, b) << "\n";
    return 0;
}

이 코드를 말씀하시는거죠?

(ret*ret)%c부분에서 (ret%c*ret%c)

>> 이미 ret은 %c가 먹여져서 리턴을 하게 됩니다. 그렇기 때문에 (ret * ret) % c를 해도 됩니다.

그리고 10번줄에 if(2)도 true인데 if(1)홀수일떄만 작동된다고 하셨는데

>> if(2)는 true지만 지금 보시면 모듈러 연산으로 홀수인지를 가리고 있는데요. 만약 2 % 2를 하게 되면 0이 되서 false, 짝수일 때는 작동되지 않습니다.

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

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

감사합니다.

강사 큰돌 올림.

ll go(ll a, ll b){
    if(b == 1) return a % c;
    ll ret = go(a, b / 2);
    ret = (ret * ret) % c;
    if(b % 2)ret = (ret * a)% c;
    return ret;
}

    ll ret = go(a, b / 2);

    if(b == 1) return a % c;

    ret = (ret * ret) % c;

    if(b % 2)ret = (ret * a)% c;