1-N 분배법칙 질문

답변주신 내용에 ret은 이미 %c가 된 상태로 나온다는게 이해가 가질 않습니다. 

>>

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

코드를 보시면 가장 마지막 기저사례에서 모듈러 연산을 한 ret이 나오게 됩니다.

마지막 부분만을 생각해볼까요?

그렇게 나온 ret이 다시 곱하면서 %c를 하게 되죠?

이 때는 (ret * ret) % c; 이렇게 해도 됩니다.

왜냐면 마지막에 나온 a%c가 ret으로 나오게 되는데 이는 모듈러 연산이 적용된 변수이기 때문입니다.

그리고 나서.. 누적으로 ~ 쌓여서 ret이 완성되는 것이죠.

예를 들어 11이 있는데 그걸 %10을 하게 되면 1이 되는데

1 * 1 을 해도 각각 다시 % 10을 안해도 되는 것이죠.

감사합니다.

인프런에서 *을 연속해서 쓰면 기울임 처리되어 곱하기를 x로 나타내겠습니다

답변주신 내용에 ret은 이미 %c가 된 상태로 나온다는게 이해가 가질 않습니다. 

원래 개념 설명에서는

A^B % C 은

(A x A x A ... ) % C 인데

이렇게 하지 말고

(A%C x A%C x A%C x A%C ... ) 해서 A끼리 곱할때 발생할 수 있는 오버 플로우를 없애자는 개념이였습니다.

다시 코드로 돌아와서

ret = (ret * ret) % C 하게 되면

ret * ret이 먼저 계산되니까

결국 A%C * A%C가 아닌

(A * A) % C 으로 계산되어 분배법칙이 안쓰인 것이 아닌가요?

안녕하세요 ㅎㅎ

    //ret = (ret * ret) % c;

    ret = ret % c * ret % c;

ret은 이미 %c 인 상태로 나오게 됩니다.

이 상태에서 ret 을 한번 더 곱하면 기존 ret보다 더 큰수가 되기 때문에 %c를 헤주어야 합니다.

만약 이렇게 하실거면.

    ret = ret % c * ret % c;

앞의 코드가 아니라 이렇게 해주셔야 합니다.

    ret = (ret % c * ret % c)% c;

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

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

감사합니다.

강사 큰돌 올림.