오일러 phi 함수 재활 -xφ(x) = n을 만족하는 x의 최솟값 구하기-

1. 문제

 

19577번: 수학은 재밌어 (acmicpc.net)

19577번: 수학은 재밌어

 

 

2. 풀이

 

오일러 phi함수를 구하는 방법

 

n을 소인수분해해서 소인수를 이용해 구하는 방법이 $O(\sqrt{n})$으로 빠르다

 

https://deepdata.tistory.com/571

오일러의 phi 함수 직접 구현해보면서 개념 익히기

 

너무 오랜만에 써봐서 기억이 안남...

 

대충 n이하의 n과 서로소인 수의 개수를 세는 함수인데 소인수 p를 구해서

 

result//p를 result = n에서 계속 빼가는 방식으로 구현

 

def phi(n):
    
    result = n

    p = 2

    while p*p <= n:
        
        if n % p == 0:
            
            while n % p == 0:
                
                n = n//p
            
            result -= result//p
        
        p += 1
    
    if n > 1:
        
        result -= result//n
    
    return result

 

이게 성질이 여러가지 있다보니까 n이 주어질때 xφ(x) = n을 만족하는 x를 구하는 방법이 뭐 있나했는데

 

딱히 없더라고.. 이걸로 괜히 고민하다가 시간 많이 잡아먹음..

 

컴퓨터의 가장 큰 무기는 하나부터 다 조사해보는것

 

쉽게 생각하는게 문제 해결의 답일 수 있다는거

 

xφ(x) = n은 결국 n이 두 정수 x와 φ(x)의 곱으로 나타낼 수 있는가이다.

 

그러면 n의 약수를 $O(\sqrt{n})$에 하나부터 순회해서 그것을 i라고 할때, 다른 하나는 n//i니까..

 

φ(i) = n//i인가? φ(n//i) = i인가? 두가지를 검사하면 되겠지

 

φ(i) = n//i이면 x = i가 될거고 φ(n//i) = i이면 x = n//i가 정답일거고

 

n = int(input())

find = False
answer = 0

for i in range(2,int((n**(1/2)))+1):
    
    if n % i == 0:
        
        x = n//i

        if phi(i) == x:

            find = True
            answer = i
            break
        
        elif phi(x) == i:
            
            find = True
            answer = x
            break

if find:
    
    print(answer)

elif n == 1 or n == 2:
    
    print(n)

else:
    
    print(-1)

 

근데 이렇게하면... 복기해보니까 반례가 있을것 같다는 생각을 했는데

 

for i in range(2,int((n**(1/2)))+1):
    
    if n % i == 0:
        
        x = n//i

        if phi(i) == x:

            find = True
            answer = i
            break
        
        elif phi(x) == i:
            
            find = True
            answer = x
            break

 

위에서 모든 경우를 검사하지 않고

 

φ(i) = n//i인가? φ(n//i) = i인가? 두가지를 검사해서

 

φ(i) = n//i이면 x = i가 될거고 φ(n//i) = i이면 x = n//i가 정답이라고 바로 break해버렸잖아

 

근데 두번째 경우인 "φ(n//i) = i이면 x = n//i가 정답" 이 부분에서 반례가 있지 않을까 생각을 했단말이야

 

φ(n//i) = i가 맞지만, i보다 크지만 n//i보다 작은 어떤 j에 대하여 φ(j) = n//j를 만족한다면.. 

 

j가 최소의 x가 되니까 j가 정답이잖아

 

이런 경우가 있지 않을까 생각했는데 브루트포스로 검사해보니까 없더라?? 왜 없는지 모르겠지만

 

아무튼 이런 경우를 피하기 위해 모든 경우를 검사하는 코드도 통과하긴함

 

def phi(n):
    
    result = n

    p = 2

    while p*p <= n:
        
        if n % p == 0:
            
            while n % p == 0:
                
                n = n//p
            
            result -= result//p
        
        p += 1
    
    if n > 1:
        
        result -= result//n
    
    return result

n = int(input())

answer = n

for i in range(2,int((n**(1/2)))+1):
    
    if n % i == 0:
        
        x = n//i

        if phi(i) == x:
            
            if answer > i:
                
                answer = i
        
        elif phi(x) == i:
            
            if answer > x:
                
                answer = x

if answer != n:
    
    print(answer)

elif n == 1 or n == 2:
    
    print(n)

else:
    
    print(-1)

 

 

아무튼 모르겠으면 하나하나 다 검사해보는것부터 쉽게 생각하자..

 

처음부터 세련되게 접근할려고 하지 말고