백준 1629번: 곱셈

곱셈
 
행렬곱셈 문제 풀며 썼던 분할정복.
 
처음엔 홀수일 때

long long int ret = (a * ab_2 * ab_2) % C;

이런식으로 했더니 계속 오버플로우가 났고 나는 그냥 어리둥절하고만 있었다.

long long int ret = (a * ((ab_2 * ab_2) % C) % C;

사실상 이렇게 했어야 했는데,
아무래도 코드를 잘 정리해 두어야 하는 이유가 아닌가 싶다.
 

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

#define ll long long int
ll A, B, C;

ll times(ll a, ll b) {
	if (b == 1) return a % C;

	ll ab_2 = times(a, b / 2) % C;
	ll ret = (ab_2 * ab_2) % C;

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


int main() {
	cin.tie(NULL)->sync_with_stdio(false);
	cin >> A >> B >> C;
	A %= C;
	cout << times(A, B) << endl;
	return 0;
}