탐색 범위를 줄여야하는 브루트포스 연습3 - 해밍 수열의 i번째 수 찾기

7868번: 해밍 수열

 

3개의 소인수 p1,p2,p3이 주어질 때 p1,p2,p3만으로 소인수를 가지는 자연수의 오름차순 배열에서 i번째 수를 찾는 문제

 

H(2,3,5)는 2,3,4,5,6,8,9,10,12,... 

 

p1,p2,p3,i가 10^18보다 작다고 하니까 단순하게 다 돌려보는건 어려울것 같고

 

p1,p2,p3만을 소인수로 가지니까 H(p1,p2,p3)는 $p1^{n1} * p2^{n2} * p3^{n3}$

 

여기서 출력하는 수가 10^18보다 작다고 하니까 결국 $p1^{n1} * p2^{n2} * p3^{n3}$도 10^18보다 작아야함

 

따라서 n1,n2,n3 < 60인데, 이유는 가장 작은 소수 2^60이 10^18보다 크기 때문이다

 

따라서 p1,p2,p3가 주어질때 0~59 * 0~59 * 0~59로 3중 for문 돌아보면서 

 

p1**n1 * p2 ** n2 * p3 ** n3가 1보다 크고 10^18보다 작은 경우만 담은 다음 정렬하고 i번째 수를 찾으면 끝

 

p1,p2,p3,i = map(int,input().split())

A = []

for n1 in range(60):
    
    for n2 in range(60):
        
        for n3 in range(60):

            v = (p1**n1)*(p2**n2)*(p3**n3)

            if v > 1 and v < 10**18:

                A.append(v)
            
            elif v >= 10**18:
                
                break

A.sort()

print(A[i-1])