백준 15377번 [Bounce Bounce Bounce](C++)-yes6686- 티스토리

백준 문제 풀이: 15377 [Bounce Bounce Bounce]

---

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

문제 설명:

주어진 정수 n에 대해 n + 1의 오일러 피 함수(Euler's Totient Function) 값을 구하는 문제입니다. 오일러 피 함수는 1부터 n까지의 자연수 중에서 n과 서로소인 수의 개수를 계산합니다.

---

문제 해결 코드

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

set<int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        n += 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);
        }
        
        // 소수들의 (p-1)을 곱하기
        for (auto iter = s.begin(); iter != s.end(); iter++) {
            ans *= (*iter - 1);
        }
        
        s.clear();
        cout << ans << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 오일러 피 함수 계산을 위해 주어진 수 n + 1을 소인수분해하고, 소수의 정보를 이용해 계산합니다.
• 구현 세부사항:
  • 입력된 수 n에 대해 n + 1을 계산
  • 소인수분해를 수행하며 오일러 피 함수 값을 업데이트
  • 소수 집합(set)을 이용해 중복 계산을 방지
• 시간 복잡도: O(T * √n)
  • 각 테스트 케이스마다 소인수분해의 시간 복잡도는 √n
  • 집합(set)의 삽입과 순회는 각 소수에 대해 상수 시간에 가깝게 수행

---

결과

주어진 수에 대해 n + 1의 오일러 피 함수 값을 정확히 계산하고 출력합니다. 효율적인 소인수분해 알고리즘과 집합(set)을 활용하여 구현되었습니다.

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