백준 19577번: 수학은 재밌어 (C++)

https://www.acmicpc.net/problem/19577

19577번: 수학은 재밌어

---

Solved By: Euler Phi Function

 

xφ(x) = n에서 얻어낼 수 있는 정보는 x는 n의 약수라는 것입니다. 즉, n 이하의 모든 양의 정수를 탐색할 필요가 없다는 뜻입니다.

n의 약수를 전부 얻어낼 수 있게 코드를 짭니다.

다음은 Euler Phi를 구현해야 하는데 이전 문제에서는 계속 폴라드 로를 사용해서 구현을 했었는데 소인수의 개수를 알 필요 없이 어떤 소인수만 가지는지 알면 되기 때문에 폴라드 로를 사용하지 않고 구해봅시다.

 

(출처: https://nevertheless-intheworld.tistory.com/17)

코드를 보면 n != 1이 아닌 조건에서 한 번 더 오일러 피 함수 계산을 해줍니다. 그런데 왜 한 번인가요?

이 질문에 대한 답은 가정을 해보면서 답을 구했습니다. 아래의 코드에 주석으로 달아두었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int eulerPhi(int n){
    int ret = n;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            ret *= (i - 1);
            ret /= i;
            while(n % i == 0) n /= i;
        }
    }
    // 왜 한 번 밖에 체크 하지 않나?
    // n이라는 합성수의 약수 중 sqrt(n)이상의 소수는
    // 최소 1번만 나올 수 밖에 없다.
    // n = p0 * p1이라고 가정하고, p는 소수,
    // p0 <= sqrt(n), p1 >= sqrt(n)이라고 하면
    // 다른 소수의 조합으로는 n을 만들 수가 없기 때문이다.
    if(n != 1){
        ret *= (n - 1);
        ret /= n;
    }
    return ret;
}

int main(){
    int n; cin >> n;
    
    vector<int> factors;
    for(int i = 1; i * i <= n; i++){
        if(n % i == 0){
            factors.push_back(i);
            if(n / i != i){
                factors.push_back(n / i);
            }
        }
    }
    sort(factors.begin(), factors.end());
    for(auto v : factors){
        if(v * eulerPhi(v) == n){
            cout << v;
            return 0;
        }
    }
    
    cout << -1;
    return 0;
}