[백준 / BOJ][Python] 1557 - 제곱 ㄴㄴ

[백준 / BOJ][Python] 1557 - 제곱 ㄴㄴ

https://www.acmicpc.net/problem/1557

문제 풀이

 재밌어 보여서 풀기 시작한 문제. 난이도에 비해 정말 금방 풀었다. 30분 조금 덜 걸린 거 같다. 임의의 수 X에 대해 X 이하의 자연수 중 제곱수를 인수로 갖는 수의 개수를 빼고, 남은 수의 개수가 K라면 X가 정답이다. 이는 이분 탐색을 통해 logX에 구할 수 있고, 남은 수의 개수를 빼는 과정은 전처리 해둔 소인수 배열과 포함 배제의 원리를 통해 빠르게 구할 수 있다. c^2을 X에서 뺄 때, c의 소인수가 홀수개라면 빼주고, 짝수개라면 더해줘야 한다. 그리고 만약 c가 제곱수를 인수로 갖는다면, 이미 처리되었을 것이기 때문에 그냥 넘어가면 된다. 정말 오랜만에 다이아 자력솔에 성공한 듯한 느낌이라 꽤나 기억에 남을 듯한 문제. 

코드

import sys
input = sys.stdin.readline

n = 50000
num = list(range(n + 1))
for i in range(2, n + 1):
    if num[i] == i:
        num[i * i:n + 1:i] = [i] * len(num[i * i:n + 1:i])
factor = [set() for _ in range(n + 1)]
for i in range(1, n + 1):
    x = i
    while x != 1:
        if num[x] in factor[i]:
            factor[i] = set()
            break
        factor[i].add(num[x])
        x //= num[x]
k = int(input())
lo, hi = 1, 50000 ** 2
while lo <= hi:
    mid = (lo + hi) // 2
    cnt = mid
    for i in range(2, int(mid ** 0.5) + 1):
        if not factor[i]:
            continue
        elif len(factor[i]) % 2 == 0:
            cnt += int(mid / (i ** 2))
        else:
            cnt -= int(mid / (i ** 2))
    if cnt < k:
        lo = mid + 1
    else:
        hi = mid - 1
print(lo)