백준 4355번 [서로소](C++)-yes6686- 티스토리

백준 문제 풀이: 4355 [서로소]

---

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

문제 설명:

양의 정수 n이 주어졌을 때, n과 서로소인 n 이하의 양의 정수의 개수를 구하는 문제입니다. 서로소는 두 수의 최대공약수가 1인 관계를 의미합니다. n이 0이면 프로그램을 종료하며, n이 1일 때는 결과가 0입니다.

---

문제 해결 코드

#include <iostream>
#include <set>
using namespace std;

set<int>s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;
        if (n == 1) {
            cout << 0 << '\n';
            continue;
        }
        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<int>::iterator iter;
        for (iter = s.begin(); iter != s.end(); iter++) {
            ans *= (*iter - 1);
        }
        s.clear();
        cout << ans << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 오일러 파이 함수(φ)를 활용하여 n 이하의 서로소인 수의 개수를 계산합니다.
• 구현 세부사항:
  • 입력된 n이 1일 경우 결과는 0입니다.
  • 오일러 파이 함수는 소인수를 통해 계산되며, 반복문을 사용해 n을 소인수로 나눕니다.
  • 각 소인수에 대해 φ(n)의 공식을 적용하여 결과를 계산합니다.
  • 최종적으로 계산된 값을 출력합니다.
• 시간 복잡도:
  • 소인수 분해: O(√n)
  • 오일러 파이 함수 계산: 약수 개수에 비례하여 O(k log k) (k는 약수의 개수)

---

결과

주어진 n에 대해 n과 서로소인 양의 정수의 개수를 계산하고 출력합니다. 오일러 파이 함수를 활용하여 효율적으로 문제를 해결했습니다.

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