-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
1-N 분배법칙 질문
24.02.05 18:41 작성 조회수 170
0
*, %는 연산자 우선순위가 같으니까
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;
}
답변을 작성해보세요.
0
큰돌
지식공유자2024.02.07
답변주신 내용에 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을 안해도 되는 것이죠.
감사합니다.
0
ab
2024.02.06
인프런에서 *을 연속해서 쓰면 기울임 처리되어 곱하기를 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 으로 계산되어 분배법칙이 안쓰인 것이 아닌가요?
0
큰돌
지식공유자2024.02.06
안녕하세요 ㅎㅎ
//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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 3