[백준] 1629번 곱셈 C++

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

1629번: 곱셈

 

내 풀이의 문제점) recur(a,b,c)가 recur(a,b-1,c)를 부르는 식이니 시간 복잡도는 O(b)가 걸려서 최대 20억 정도에 해당하는 수를 처리하기에는 시간이 너무 든다.

 

바킹독님 강의 보고 힌트

중요 포인트) a^n*a^n = a^(2n)

그리고 나머지 계산 방법의 원리(10진수 곱한거 나머지는 어떻게 하지?->이걸 생각하면 된다!)

 

바킹독님 코드는

#include <iostream>

using namespace std;

using ll = long long;

ll POW(ll a, ll b, ll m)
{
	if (b == 1) return a % m;

	ll val = POW(a, b / 2, m);
	val = val * val % m;
	if (b % 2 == 0) return val;
	return val * a % m;
}
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll a, b, c;
	cin >> a >> b >> c;
	cout << POW(a, b, c);
}

 

시간 복잡도를 O(logN)으로 확 줄일 수 있다.

 

출처)바킹독님 강의 및 코드는

강의 https://blog.encrypted.gg/943

[실전 알고리즘] 0x0B강 - 재귀