GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결
알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub.
github.com
Euler's phi function은 다음과 같이 정의된다.
ϕ(n) = n과 서로소인 1부터 n까지의 정수의 개수
naive하게 구하면 O(NlogN)이지만 소인수분해를 하면 O(sqrt(N))에 구할 수 있다.
끝
'알고리즘' 카테고리의 다른 글
| Network Flow 알고리즘 (0) | 2022.10.12 |
|---|---|
| Euler's theorem (0) | 2022.10.06 |
| Union-Find (0) | 2022.10.04 |
| Order Statistic Tree (0) | 2022.10.01 |
| Fenwick Tree (0) | 2022.09.30 |
