1-N 분배법칙 질문

Question

*, %는 연산자 우선순위가 같으니까 6:00 부근쯤 설명한 분배법칙을 적용하려면 해당 코드를 변경(주석처리 부분)해야 하는것 아닌가요?   typedef long long ll; ll go(ll a, ll b, ll c) { if (b == 1) { return a % c; } ll ret = go(a, b / 2, c); //ret = (ret * ret) % c; ret = ret % c * ret % c; if (b % 2) { ret = (ret * a) % c; } return ret; }

kundol · Answer

답변주신 내용에 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을 안해도 되는 것이죠.   감사합니다.

ab · Answer

인프런에서 *을 연속해서 쓰면 기울임 처리되어 곱하기를 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 으로 계산되어 분배법칙이 안쓰인 것이 아닌가요?

kundol · Answer

안녕하세요 ㅎㅎ //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점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.