[BOJ] 1629_곱셈.cpp

# 생각

매우 큰 단위이므로 int가 아닌 long long으로 선언해줘야 한다

 

2^10은 2^5 * 2^5로 구할 수 있기 때문에

재귀식을 이용하여 절반을 곱해준 결과의 나머지를 반환 해주면 된다

 

단, 홀수일 경우 곱할 수를 다시 곱해줘야하고 짝수일 경우에는 그대로 반환해주면 된다

 

 

# 전체 코드

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

typedef long long ll;

void fastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); }

ll power(ll a, ll b, ll c)
{
	if (b == 1)
	{	// base condition
		return a % c;
	}

	ll ans = power(a, b * 0.5, c);
	ans = (ans * ans) % c;
	if (b & 1)
	{
		return ans * a % c;
	}
	else
	{
		return ans;
	}
}

int main()
{
	fastIO();
	ll a, b, c;
	cin >> a >> b >> c;
	cout<< power(a, b, c);
}

 

---

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