[백준 19577번] 수학은 재밌어 (C++/c++)

 

 

---

백준 19577번
수학은 재밌어

 

www.acmicpc.net/problem/19577

19577번: 수학은 재밌어

 

아래 코드는 문제를 읽자마자 바로 생각난 대로, 간단하게 풀어본 방법입니다.

gcd를 통해 최대 공약수가 1인 값들의 cnt를 세고, 이 cnt를 오일러 피 함수의 값으로 봤습니다.

이 값을 문제에서 요구하는 값으로 조합하여 정답을 return 했습니다. 

 

풀면서 아 시간 초과 나겠다 싶었고, 당연히 시간 초과가 났어요.

gcd 함수를 통해 최대 공약수를 찾는 과정도 오래 걸리며, 그 겉을 감싸아 cnt를 세는 fn의 for문도 시간 초과의 주범입니다.

물론 이런 방법으로 오릴러 피 함수를 구현하면 이해 하기가 좋기는 합니다.

 

main함수에서 for문을 통해 input 값까지 검색하는 것도 시간초과의 문제이죠.

#include <iostream>
using namespace std;

int gcd(int a, int b){
    return b == 0 ? a : gcd( b, a % b);
}

int fn(int x)
{
    int cnt = 0;
    for(int i = 1; i < x; i++)
    {
        if (gcd( x, i) == 1)
        {cnt++;}
    }
    return cnt; 
}

int main()
{
    int input = 0;
    cin >> input;
    for(int i = 1; i <= input ; i++)
    {
        if(input%i == 0 && i * fn(i) == input)
        {
            cout << i; 
            return 0;
        }
    }

    cout << -1;
    return 0;
}

 

개선 방안을 생각해 볼때 값이 input = n * f(n)으로 만들어 져야 한다는 점에 주목했어요.

즉 n은 input의 약수인 거죠.

어떤 값의 약수를 찾을 때 log(n)이면 해당 값의 모든 약수를 구할 수 있답니다.

그렇게 약수들을 찾고, sort함수로 정렬을 해주었어요.

또한, 아래코드에서는 오일러 피 함수 구하는 방식을 log(n)정도가 걸리게 만들었어요.

fn함수 입니다. 이 함수에 대한 자세한 설명은 나중에 백준 11689번에 대한 해설을 올릴 때 자세히 해 드릴게요!

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;
vector<int> arr;

int fn(int n)
{
    int phi = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            phi /= i;
            phi *= (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n != 1) {
        phi /= n;
        phi *= (n - 1);
    }
    return phi;
}

int main()
{
    int input = 0;
    cin >> input;
    
    for(int i = 1; i * i <= input; i++){
        if(input % i == 0) {
            arr.push_back(i);
            if(i != input/i) arr.push_back(input/i);
        }
    }
    
    sort(arr.begin(), arr.end());

    for(int i = 0; i < arr.size(); i++)
    {
        if(arr[i] * fn(arr[i]) == input)
        {
            cout << arr[i]; 
            return 0;
        }
    }

    cout << -1;
    return 0;
}