[BOJ 30510 // C++] 토마에 함수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 30510번 문제인 토마에 함수이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/30510

 

이 문제는 Thomae's Function(토메 함수)을 소재로 한 문제이다. Thomae's Function은 모든 유리수점에서 불연속이고 무리수점에서 연속인 함수로, 자세한 설명은 이 문제의 해결에 필요한 범주를 넘어서므로 생략한다.

 

\(f\)의 함숫값은 (0을 제외하면) 항상 단위분수의 형태로 나타남을 관찰하자. 따라서 조건을 만족시키는 실수 \(x\)의 함숫값으로 나타날 수 있는 주어진 수보다 큰 단위분수 \(\frac{1}{N}\)을 이분탐색으로 먼저 구한다면, 조건을 만족시키는 \(x\)들(0 제외)은 분모가 \(N\) 이하인 기약분수(\(\frac{1}{1}\) 포함)의 형태로 나타남을 관찰하자.

 

이와 같은 \(x\)의 개수는 Euler Totient Function을 이용해 빠르게 계산할 수 있다. Euler Totient의 함숫값은 Sieve of Eratosthenes(에라토스테네스의 체)와 같은 방식으로 빠르게 전처리할 수 있음을 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

//30510: Euler Phi
#include <iostream>
using namespace std;
typedef long long ll;

ll P, Q, L = 1, R = 100000;
bool sieve[100001];
ll eulerphi[100001];

void init() {
    sieve[0] = sieve[1] = 1;
    for (int i = 2; i * i < 100001; i++) {
        if (sieve[i]) continue;
        for (int j = i * i; j < 100001; j += i) sieve[j] = 1;
    }
    for (int i = 1; i < 100001; i++) eulerphi[i] = i;
    for (int i = 1; i < 100001; i++) {
        if (sieve[i]) continue;
        for (int j = i; j < 100001; j += i) {
            eulerphi[j] /= i;
            eulerphi[j] *= i - 1;
        }
    }
}

ll ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> P >> Q;
    while (L < R) {
        ll mid = (L + R) / 2 + 1;
        if (Q >= P * mid) L = mid;
        else R = mid - 1;
    }

    init();
    for (int i = 1; i <= L; i++) ans += eulerphi[i];
    cout << ans + 1;
}