백준24403 Common Factors

작성일 | In

문제 링크

  • http://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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

bool IsPrime(int n){
    if(n < 2) return false;
    for(int i=2; i*i<=n; i++) if(n % i == 0) return false;
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    long long n, p = 1, q = 1;
    cin >> n;
    for(int i=2; ; i++){
        if(!IsPrime(i)) continue;
        if((__int128_t)q * i <= n) p *= i - 1, q *= i;
        else break;
    }
    p = q - p;
    auto g = __gcd(p, q);
    cout << p / g << "/" << q / g;
}