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

#include <bits/stdc++.h>
using namespace std;

long long a, b, c;

long long multi(long long num) {
	if (num == 1) {
		return a % c;
	}
	long long sum = (multi(num / 2) * multi(num / 2));
	if (num %2) sum*=a%c;
	return sum % c;
}

int main()
{
	cin >> a >> b >> c;
	cout << multi(b);
}

재귀함수 코드를 위와 같이 작성해서 제출했는데 틀렸습니다가 나왔습니다. 하지만 long long sum~ 여기 줄에서 마지막에 c로 나눠주면 통과가 됩니다. 저는 어차피 마지막에 한번 c로 나눠주어 리턴하기 때문에 문제가 안될 거라고 생각했는데 홀수인 경우에 a%c를 한번 더 곱하면 범위를 넘어서서 틀리는 건가요??