전체 글178 백준 14854 - 이항 계수 6 step 1 더보기 $142857=3^3*11*13*37$입니다. 만약 어떤 수 $n$에 대해 27,11,13,37로 나눈 나머지를 알 수 있다면 $n$을 142857로 나눈 나머지도 알 수 있습니다. step 2 더보기 ${n \choose k} = \frac{n!}{k!(n-k)!}$를 27로 나눈 나머지에 대해서만 생각해 봅시다. 만약 소인수분해를 했을 때 3이 3개 이상 나온다면 나머지는 0입니다. 이는 $O(log\ n)$에 해결할 수 있습니다.(https://codestudycafe.tistory.com/1) 어떤 수를 소인수분해를 하면 $2^{x_1}* 3^{x_2}* 5^{x_3} ..$ 식으로 나옵니다. 3이 몇 개 나오는지는 알았으니 나머지에 대해서만 생각하면 됩니다. $f(x) = n.. 2024. 3. 16. x/y (mod n) 계산 오일러 정리에 의하면 $a^{\varphi(n)} \equiv 1\pmod{n}$ 입니다. 이때 $\varphi(n)$(오일러 피 함수)은 1부터 $n$까지의 수 중 $n$과 서로소인 수의 개수입니다. $a$와 $n$이 서로소일 때만 가능합니다. 오일러 피 함수 구하기 더보기 $\varphi(n)$ 는 몇가지 특징이 있어 생각보다 쉽게 구할 수 있습니다. $p$가 소수일 때 $\varphi(p) = p-1$ $\varphi(pq)= \varphi(p) * \varphi(q) $ $ \varphi(p^n)=p^n - p^{n-1} $ 이를 잘 이용하면 소인수분해를 이용해서 구할 수 있습니다. 오일러 정리를 이용하면 모듈러 연산에서 나눗셈을 할 수 있습니다. $\begin{matrix} &a^{\varphi.. 2024. 3. 16. 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$으로 나눈 나머지를.. 2024. 3. 16. 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.. 2024. 3. 16. 이전 1 ··· 27 28 29 30 다음