Algorithm PS/Algospot
[Algospot] 정수론 / PASS486 / Python 파이썬
migrationArc
2021. 9. 22. 15:36
https://www.algospot.com/judge/problem/read/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)
※ 파이썬은 시간제한을 통과하지 못한다... (정확히는 풀이에 성공한사람이 한명도 없었다, 안될거야 아마...)