[C++] 백준 1629. 곱셈

🌽 문제

🥕 입출력

🥔 풀이

분할 정복 단계에 들어가기 전, 유튜브에서 시청한 영상의 도움을 받았다.
겨수님의 논리를 잘 따라가둔 덕에 풀이는 금방 생각났으나
ret *= ret % c 뭐 이런 요약식의 오류 때문에
맞았습니다를 하ㄴ참 지나서 볼 수 있었다.

🥬 코드

#include <iostream>
using namespace std;

int a, b, c;

long long solution(long long base, long long exp) {
	if (exp == 0) return 1;
	long long half = solution(base, exp / 2);
	long long ret = half * half % c;
	if (exp % 2 == 1) ret = ret * base % c;
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> a >> b >> c;
	cout << solution(a, b);
	return 0;
}

🥜 채점

정답 풀기시른사람