[백준 1629] 곱셈

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

 

정답 코드

using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b) {
	cout << a << ":" << b << '\n';
	if (b == 1) return a % c;
	ll ret = go(a, b / 2);
	ret = (ret * ret) % c;
	if (b % 2)
	{
		ret = (ret * a) % c;
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> a >> b >> c;
	cout << go(a, b) << "\n";
	return 0;
}