[BOJ] 1629_곱셈 with cpp

# 생각

시간복잡도 : b가 계속 절반씩 깎이기 때문에 O(logb) 이다

a^n * a^n = a^2n의 성질을 이용하면 b가 최대 20억이라도 해결이 가능하다

 

 

# 전체 코드

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

LL Power(LL a, LL b, LL c)
{
	if (b == 1)	// base condition
	{
		return a % c;
	}
	LL result = Power(a, b / 2, c);
	result = result * result % c;

	if (b % 2 == 0)	// 짝수면 바로 반환
	{
		return result;
	}
	else	// 홀수면 a 한 번 더 곱해서 반환
	{
		return result * a % c;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	LL a, b, c;
	cin >> a >> b >> c;
	cout << Power(a, b, c);
}

---

https://www.acmicpc.net/problem/1629

1629번: 곱셈