분류 전체보기 (152) 썸네일형 리스트형 x^n 을 O(log n)에 구하기 $x^n$을 단순히 for문으로 구한다고 하면 $O(n)$만큼의 시간이 걸립니다. 이를 분할정복을 이용해서 빠르게 구할 수 있습니다. $2^{100}$을 구한다고 해보겠습니다. $2^{100} = 2^{50} * 2^{50}$입니다. 그럼 $2^{50}$을 구한다면 그 수를 제곱해서 $2^{100}$을 구할 수 있습니다. 마찬가지로 $2^{50} = 2^{25} * 2^{25}$입니다. 그럼 $2^{25}$을 구한다면 그 수를 제곱해서 $2^{50}$을 구할 수 있습니다. $2^{25}$는 2로 나누어지지 않습니다. 이런 경우에는 $2^{12}*2^{12}*2$를 이용하면 됩니다. 이런 식으로 진행하면 $O(log n)$에 구할 수 있습니다. 보통 이런 종류의 문제는 $x^n$을 $m$으로 나눈 나머지를.. N!에서 소수 p 등장 횟수 구하기 $ N! $ 을 소인수분해 했을 때 소수 $ p $ 가 몇 번 나오는지 찾는 알고리즘입니다. $ N $ 을 $ p $ 로 나눈 몫을 구합니다. 1에서 $ N $ 까지의 숫자 중 $ p $ 를 소인수로 가지는 수의 개수를 구할 수 있습니다. $ N $ 을 $ p^2 $로 나눈 몫을 구합니다. 1에서 $ N $ 까지의 숫자 중 $p^2$ 를 소인수로 가지는 수의 개수를 구할 수 있습니다. 이런 식으로 몫이 0이 될 때 까지 계속 합니다. 나온 숫자를 모두 더해줍니다. #include using namespace std; int main() { int n, p, cur_p, count = 0; cin >> n >> p; cur_p = p; while (n / cur_p != 0) { count += n / c.. 이전 1 ··· 13 14 15 16 다음