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

#include <bits/stdc++.h>

using namespace std;

long long A, B, C;
long long go(long long a, long long b)
{
    if (b == 1) 
    {
        return a % C;
    }

    long long ret = go(a, b / 2);
    ret = (ret * ret) % C;    

    if (b % 2 == 1) 
    {
        ret = (ret * a) % C;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> A >> B >> C;
    cout << go(A, B) << '\n';
}

B가 홀 수 일 때, 홀수 처리를 하기 직전

ret = A^(B-1) % C 입니다.

그러면 홀수처리가 진행 될 때

ret = ((A^(B-1) % C) * A) %C 가 코드의 상황 인데 이게 최종 결과인 A^B % C 와 같아지는게 이해가 안됩니다.

나머지 연산의 합동공식이

(a * b) % c = (a % c * b % c) % c 이기 때문에

A^B % C

= (A^(B-1) * A) % C

= (A^(B-1) % C * A % C) % C

위와 같은 식이 나와야 하고

ret = (ret * a) % C가 아니라

ret = (ret * a % C) %C 가 되어야 하는 것 아닌가요? 백준에서는 둘다 맞게 처리 되는데 이해가 되지 않습니다.