백준 11525번 [Farey Sequence Length](C++)-yes6686- 티스토리

백준 문제 풀이: 11525 [Farey Sequence Length]

---

문제 링크: https://www.acmicpc.net/problem/11525

문제 설명:

Farey 수열의 길이를 계산하는 문제입니다. Farey 수열은 분모가 n 이하인 기약 분수의 집합으로 구성됩니다. Farey 수열의 길이를 계산하려면 오일러 파이 함수(Φ)를 이용하여 서로소의 개수를 계산해야 합니다.

• Farey(n)의 길이는 Φ(1) + Φ(2) + ... + Φ(n) + 1입니다.
• 오일러 파이 함수(Φ)는 임의의 정수 m에 대해, m 이하의 정수 중 m과 서로소인 정수의 개수를 반환합니다.

예를 들어, Φ(6)은 2, 3, 4, 5 중 6과 서로소인 정수의 개수를 반환하며, 결과는 2입니다 (1과 5만 해당). Φ(n)을 빠르게 계산하기 위해 오일러 파이 함수의 성질을 사용합니다.

---

문제 해결 코드

#include <iostream>
#include <set>
using namespace std;
set s;
int dp[100001];

int euler(int n) {
    if (n == 1) return 1;
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans /= i;
            s.insert(i);
        }
        while (n % i == 0) {
            n /= i;
        }
    }
    if (n > 1) {
        ans /= n;
        s.insert(n);
    }
    set::iterator iter;
    for (iter = s.begin(); iter != s.end(); iter++) {
        ans *= (*iter - 1);
    }
    s.clear();
    return ans;
}

int go(int n) {
    if (dp[n]) return dp[n];
    dp[n] = euler(n) + go(n - 1);
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    dp[1] = 1;
    while (T--) {
        int k, n;
        cin >> k >> n;
        cout << k << " " << go(n) + 1 << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 오일러 파이 함수와 동적 프로그래밍을 활용합니다.
• 구현 세부사항:
  • euler(n): 주어진 n에 대해 오일러 파이 함수 값을 계산합니다.
  • 중복 계산을 방지하기 위해 dp 배열을 사용합니다.
  • go(n): Φ(1)부터 Φ(n)까지의 합을 반환하며, 계산된 값을 dp에 저장합니다.
• 시간 복잡도: O(T * sqrt(n) + n), T는 테스트 케이스 수, n은 최대 입력값입니다.

---

결과

주어진 n에 대해 Farey 수열의 길이를 정확히 계산합니다. 오일러 파이 함수와 동적 프로그래밍을 조합하여 효율적으로 해결했습니다. 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!