[BOJ 19577] 수학은 재밌어

문제 제목부터 공감이 간다.

아무튼 문제를 풀어보자.

어떤 양의 정수 $n$이 있다고 할 때, $x\phi(x) = n$을 만족하는 양의 정수 $x$가 존재하는가?

 

이때 $\phi(x)$는 오일러 피 함수이다. 사실 이 문제는 매우 간단하다! $x$가 $n$을 나누기 때문에 $n$의 약수를 찾으면 된다. 또 $\phi(x)$를 계산해야하는데 이는 $x$를 인수분해 하면 되고 $O(\sqrt{x})$이 걸린다. $n$의 약수를 인수분해 하므로 $n$의 가장 큰 약수가 시간복잡도에 지배적이라고 보면 $O(\sqrt{n})$이라고 볼 수 있다. 약수를 찾는과정은 $O(\sqrt{n})$의 시간이 걸린다. 따라서 전체 시간 복잡도는 $O(2\sqrt{n})$이다.

오일러 피 함수 설계 방식을 설명하겠다. 이해가 안된다면 오일러 피 함수의 계산법을 찾아보자.

먼저 $x$의 가장 작은 소인수를 찾고 $x$를 소인수로 나눈다. 방금 찾은 소인수로 나누어지면 위 과정을 반복한다. 나누어지지 않으면 새로운 소인수를 i를 1씩 증가시키며 찾는다. 그 인수가 소수인지 판정하기 위해 sosu라는 함수를 만들었으며 소수가 아니라면 그 인수를 나누는 소수를 반환한다.

이렇게 $n$의 약수 중 조건을 만족하는 최소의 정수를 찾으면 된다. 만약 없다면 -1을 출력한다.

 

코드는 아래에 있다.

 

# 코드 보기

#include<stdio.h>
typedef long long int lo;
#define lim 1e10
lo min(lo a,lo b){
    return a>b?b:a;
}
lo sosu(lo n){
    if(n==1) return 1;
    if(n%2==0) return 2;
    for(lo i=3;i*i<=n;i+=2) if(n%i==0) return i;
    return n;
}
lo pi(lo n){
    lo a=1,i,c=0,t;
    for(i=2;n-1;i++){
        if(n%i==0){
            n/=i;
            a*=c!=i?i-1:i;
            c=i--;
        }
        i=sosu(n)-1;
    }
    return a;
}
int main(){
    lo n,i,x;
    scanf("%lld",&n);
    x=lim;
    for(i=1;i*i<=n;i++){
        if(n%i==0){
            if(i*pi(i)==n) x=min(x,i);
            if(n/i*pi(n/i)==n) x=min(x,n/i);
        }
    }
    printf("%lld",x==lim?-1:x);
}

# 닫기