백준 11689번 [GCD(n, k) = 1](C++)-yes6686- 티스토리

백준 문제 풀이: 11689 [GCD(n, k) = 1]

---

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

문제 설명:

양의 정수 n이 주어졌을 때, 1부터 n까지의 정수 중 n과 서로소인 정수의 개수를 구하는 문제입니다. 서로소는 두 수의 최대공약수(GCD)가 1인 관계를 의미합니다. 이를 구하기 위해 오일러 파이 함수(φ)를 활용합니다.

---

문제 해결 코드

#include <iostream>
#include <set>
using namespace std;
set<long long int>s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    long long int n;
    cin >> n;
    long long int ans = n;
    for (long long 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<long long int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); iter++) {
        ans *= (*iter - 1);
    }
    cout << ans;
}

---

코드 설명

• 핵심 알고리즘: 오일러 파이 함수(φ)를 이용하여 n과 서로소인 정수의 개수를 구합니다.
• 구현 세부사항:
  • 입력된 n의 소인수를 구하기 위해 2부터 √n까지 반복하며 소인수들을 추출합니다.
  • 오일러 파이 함수의 공식 φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ...을 활용하여 결과를 계산합니다.
• 시간 복잡도:
  • 소인수 분해: O(√n)
  • 오일러 파이 함수 계산: 소인수의 개수에 비례하여 O(k), k는 소인수의 개수

---

결과

주어진 n에 대해 1부터 n까지의 정수 중 n과 서로소인 정수의 개수를 효율적으로 계산했습니다. 오일러 파이 함수의 개념을 적용하여 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!