[Algospot] 정수론 / PASS486 / Python 파이썬

[Algospot] 정수론 / PASS486 / Python 파이썬

https://www.algospot.com/judge/problem/read/PASS486#

algospot.com :: PASS486

 

풀이

주어진 범위안의 수 중, 약수의 개수가 n 개가 되는 수의 개수를 구하는 문제이다.

 

먼저, 에라토스테네스의 체를 사용하여 1천만 이하의 모든 수의 가장 작은 소인수를 구한 뒤

주어진 범위의 약수의 개수를 구해주었다.

 

# 1천만 이하의 모든 수의 약수의 개수를 계산하는 알고리즘

Max = 10000000

# 가장 작은 소인수
minFactor = [x for x in range(Max+1)]
minFactor[0] = 0
minFactor[1] = 1

sqrtn = int(Max ** 0.5)

for i in range(2, sqrtn+1):
    if minFactor[i] == i:
        for j in range(i*i, Max+1, i):
            if minFactor[j] == j:
                minFactor[j] = i


# minFactorPower[i] = i 의 소인수 분해에는 minFactor[i]의 몇승이 포함되는지
minFactorPower = [0] * (Max + 1)

# factors[i] = i 가 가진 약수의 개수
factors = [0] * (Max + 1)


def getFactorsSmart():
    global Max, minFactor, minFactorPower, factors

    # 1의 약수는 1개
    factors[1] = 1

    for i in range(2, Max+1):
        # 소수인 경우
        if minFactor[i] == i:
            # i ** 1 승
            minFactorPower[i] = 1
            # 소수 [1, i] -> 2개
            factors[i] = 2
        else:
            p = minFactor[i]

            m = int(i / p)

            if p != minFactor[m]:
                minFactorPower[i] = 1
            else:
                minFactorPower[i] = minFactorPower[m] + 1

            a = minFactorPower[i]
            factors[i] = int((factors[m]/a) * (a+1))


getFactorsSmart()

C = int(input())


for _ in range(C):
    n, lo, hi = map(int, input().split())

    res = 0

    for i in range(lo, hi+1):
        if factors[i] == n:
            res += 1
    print(res)

※ 파이썬은 시간제한을 통과하지 못한다... (정확히는 풀이에 성공한사람이 한명도 없었다, 안될거야 아마...)