자료구조 및 알고리즘/백준
[백준] 1629번 곱셈 C++
아기사우르스
2023. 7. 9. 19:01
728x90
백준 1629 https://www.acmicpc.net/problem/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
728x90