def check(x):
cnt = 0; sq = 0
q = [(1,-1,1)]
while q:
n,i,s = q.pop()
for j in range(i+1,P):
n1 = n*prime[j]**2
if n1>x:
break
cnt += x//n1*s
sq |= int(not x%n1)
q.append((n1,j,-s))
return x-cnt,sq
prime = []; visited = [0]*50001
for i in range(2,50001):
if not visited[i]:
prime.append(i)
if i<317:
for j in range(1,50000//i+1):
visited[i*j] = 1
P = len(prime)
K = int(input())
x,c = 1<<31,30
while 1:
k,sq = check(x)
if k<K:
x += 1<<c
elif k>K or k==K and sq:
x -= 1<<c
else:
break
c -= 1
print(x)이분탐색 + 에라토스테네스의 체로 해결하였다.
풀이를 설명하면,
1. 에라토스테네스의 체로 1~50000 사이의 소수를 구한다.
2. 1~x 사이에 제곱수가 몇개인지 구하는 check 함수를 만든다. 각 소수들의 곱의 제곱으로 이루어진 제곱수들의 배수의 개수의 합을 구해주면 되는데, 이때 포함-배제의 원리에 따라 곱해진 소수들의 개수가 홀수면 더해주고, 짝수면 빼주어야 한다. 또, x가 제곱수의 배수인지도 확인한다.
3. 이분탐색으로 1~x 사이의 제곱ㄴㄴ수의 개수(x-제곱수 배수의 개수)가 K개이고, x가 제곱ㄴㄴ수인 x값을 찾아 출력한다.
제곱 ㄴㄴ 수[백준 1016번] 제곱 ㄴㄴ 수 (Python3) (tistory.com) 를 이미 풀어본 경험이 있어 쉽게 해결했던 것 같다. 당시에 쉽게 풀이를 떠올려놓고도 시간복잡도상 안될 것이라 단정지어서 풀지 못했었다. 이번에도 사실 check 함수의 시간복잡도가 언뜻보면 O(N^3) (N은 소수의 개수) 로 보이는데, 사실 x보다 작은 숫자에 대해서만 판별하기 때문에 훨씬 적은 시간에 통과될 수 있다.
오늘의 교훈) 숫자의 제한에 따른 시간복잡도를 면밀이 검토해야한다.