문제 링크
- https://icpc.me/24403
사용 알고리즘
- 오일러 피 함수
시간복잡도
- $O(\log^{3/2+\epsilon} n)$
풀이
$(k-\phi(k)) / k = 1 - \phi(k)/k$의 최댓값을 구하는 문제이므로 $\phi(k)/k$를 최소화하는 문제라고 생각할 수 있습니다. 이때 $\phi(k)/k = \prod_{p\vert k}(p-1)/p$입니다.
위 식을 최소화해야 하는데, 1보다 작은 양수는 곱할수록 값이 점점 작아지기 때문에 $p$들의 곱이 $n$보다 작은 범위 안에서 $p$를 최대한 많이 사용하면 됩니다. 그러므로 정답은 $1 - (1/2) - (2/3) - (4/5) - \cdots$입니다.
$n$의 소인수는 최대 $O(\log n)$개이므로 소수 정리에 의해 $O(\log n \times \log \log n)$ 까지의 소수만 구해도 충분합니다. 소수 판별을 $O(\sqrt n)$ 시간에 하면 전체 시간 복잡도는 $\int_{2}^{O(\log n\times\log\log n)}\sqrt{x} dx=O(\log^{3/2+\epsilon} n)$입니다.
전체 코드
1 |
|