백준 19577번 [수학은 재밌어](C++)-yes6686- 티스토리

백준 문제 풀이: 19577 [수학은 재밌어]

---

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

문제 설명:

양의 정수 n이 주어질 때, n의 약수 중 오일러 파이 함수 결과와의 곱이 다시 n이 되는 가장 작은 양의 정수를 출력하는 문제입니다. 만약 조건을 만족하는 값이 없다면 -1을 출력합니다.

---

문제 해결 코드

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

int euler(int n) {
    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();
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int ans = n;
    int check = n;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            x.insert(i);
            if (ans / i != i)
                x.insert(ans / i);
        }
    }
    set<int>::iterator iter;
    for (iter = x.begin(); iter != x.end(); iter++) {
        if ((*iter) * (euler(*iter)) == check) {
            cout << *iter << '\n';
            return 0;
        }
    }
    cout << -1;
}

---

코드 설명

• 핵심 알고리즘: 오일러 파이 함수(φ)를 활용하여 조건을 만족하는 약수를 탐색합니다.
• 구현 세부사항:
  • euler: 입력값의 오일러 파이 함수 값을 계산합니다. 소인수분해를 통해 계산합니다.
  • 모든 약수를 구한 뒤, 오일러 파이 함수와의 곱이 n이 되는지 확인합니다.
  • 첫 번째로 조건을 만족하는 값을 출력하고 종료하며, 없다면 -1을 출력합니다.
• 시간 복잡도:
  • 약수 계산: O(√n)
  • 오일러 파이 함수 계산: 약수 개수에 비례하여 O(k log k) (k는 약수의 개수)

---

결과

주어진 n에 대해 조건을 만족하는 가장 작은 약수를 출력하거나, 없으면 -1을 출력합니다. 오일러 파이 함수와 약수 계산을 효과적으로 구현하여 문제를 해결했습니다.

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