x^n 분할정복 (빠른 거듭제곱, c++)

stl pow() : 반환 값이 double로 나온다. 항상 유의

나이브한 반복문 풀이 : O(N) -> 시간초과 주의

분할정복 풀이 : O(logN) -> 베리 굿

 

#include <bits/stdc++.h>
using ll = long long;
//constexpr ll MOD = 1'000'000'007;

ll p(ll n)
{
	ll x = 2;
	ll res = 1;
	while(n)
	{
		if(n&1)
		{
			res *= x;
			//res %= MOD;
		}
		x *= x;
        // x %= MOD;
		n = n>>1;
	}
	return res;
}

int main()
{
	cout << p(20);
}

 

주석 부분은 문제에서 모듈로 연산을 필요로 할 때 사용 (오버플로 방지용)