약수를 세는 것보다 배수를 세는 것이 더 쉽다(홀수인 약수의 합, 유일한 소인수의 개수를 구하는 방법)

SW Expert Academy

SW Expert Academy

 

 

어떤 정수 x의 약수 중 홀수인 약수의 합을 f(x)라고 할때, L,R이 주어지면 L이상 R이하의 모든 x에 대해 f(x)의 합을 구하는 문제

 

단순한 방법으로는 소인수분해를 해서 홀수인 소인수들의 곱으로 약수의 합을 구하면 된다.

 

https://deepdata.tistory.com/588

약수의 합과 약수의 개수 공식 익히기

 

 

 

여기서 핵심은 짝수 * 홀수 = 짝수, 짝수 * 짝수 = 짝수, 홀수 * 홀수 = 홀수니까 소인수를 홀수만 남기면 홀수인 약수만 얻을 수 있다.

 

또한 모든 소수중 유일하게 2만 짝수이다.

 

그래서 1부터 1000000까지 순회하면서 먼저 2로 나누어 떨어지지 않을때까지 나눈다.

 

나누고 나서, 이를 $O(\sqrt{n})$ 소인수분해를 한다.

 

소인수의 개수를 알면 등비수열의 합 공식을 곱해나가면 약수의 합을 구할 수 있다

 

#정수 i의 홀수인 약수의 합
n = 10**6

odd_sigma = [0]*(n+1)

for i in range(1,n+1):
    
    k = i
    
    #2로 나누어 떨어지지 않을때까지 나누면 홀수인 소인수만 남는다
    while i % 2 == 0:
        
        i //= 2
    
    value = 1
    
    #소인수분해를 하면서 각 소인수의 개수를 구한다
    for j in range(3,int(i**(1/2))+1):

        if i % j == 0:
            
            count = 0
            
            while i % j == 0:
                
                i //= j
                count += 1
            
            #등비수열의 합으로 약수의 합에 누적곱을 해주면...
            value *= (j**(count+1) - 1)//(j-1)
    
    if i > 1: #i 자체가 소인수인경우
        
        value *= (1+i)
    
    odd_sigma[k] = value

 

 

$O(N\sqrt{N})$이라 N이 $10^{6}$이라 매우 느리다.. 제한시간이 14초라 8초정도로 통과하긴 한데

 

https://deepdata.tistory.com/893

1부터 n까지 모든 자연수들 각각의 약수의 누적합을 구하는 방법들(double counting, harmonic lemma, dynami

 

https://deepdata.tistory.com/807

약수의 합 아주 빠르게 찾기 - 더블 카운팅(배수를 이용해 약수를 찾기), smallest prime factor

 

 

"약수의 개수를 세는것보다, 배수를 이용하는게 더 쉽다"

 

에라토스테네스의 체에서 쓰던 것처럼 약수를 찾는것보다 배수를 찾는 방식으로 한다면?

 

루트 시간을 로그 시간으로 바꿀 수 있다

 

for i in range(2,int(n**(1/2))+1):
    
    if result[i] == 1:
        
        for j in range(i*i,n+1,i):
            
            result[j] = 0

 

 

배열 odd_sigma[i]는 정수 i의 홀수인 약수의 합이다.

 

"1,3,5,7,...의 모든 홀수 i에 대하여 i의 배수는 i를 약수로 가진다"

 

그래서 1부터 2씩 증가시켜가며 모든 홀수 i에 대하여 i의 배수는 i부터 i씩 증가시켜가며 얻을 수 있으니까...

 

n = 10**6

odd_sigma = [0]*(n+1)

for i in range(1,n+1,2):
    
    for j in range(i,n+1,i):
        
        odd_sigma[j] += i

 

 

이렇게 하면 8초 걸리는 코드를 0.4초로 단축시킬 수 있다

 

#정수 i의 홀수인 약수의 합
#i의 모든 배수는 i를 약수로 가진다.
n = 10**6

odd_sigma = [0]*(n+1)

#홀수 i에 대하여...
for i in range(1,n+1,2):
    
    #i의 배수 j는 i를 약수로 가지므로.. 이를 누적합시킨다.
    for j in range(i,n+1,i):
        
        odd_sigma[j] += i

#구간 [L,R]의 누적합을 구해야하므로 prefix sum
for i in range(1,n+1):
    
    odd_sigma[i] += odd_sigma[i-1]

T = int(input())

answer = []

for test_case in range(1, T + 1):
    
    a,b = map(int,input().split())
    
    answer.append(f'#{test_case} {odd_sigma[b] - odd_sigma[a-1]}')

print('\n'.join(answer))

 

 

 

27575번: Distinct Parity Excess (acmicpc.net)

27575번: Distinct Parity Excess

 

구간 [a,b]가 주어지면 a이상 b이하의 어떤 정수의 유일한 소인수의 개수가 홀수인 수의 개수와 짝수인 수의 개수의 차이를 묻는 문제

 

위와 비슷한 방식으로 접근할 수 있다.

 

1은 소수가 아니니까 2부터 최대 $10^{7}$까지 모든 정수 i에 대하여...

 

현재 i가 사용되지 않았다면... 해당 i는 소수이며 

 

이 소수 i의 배수는 모두 i를 인수로 가진다.

 

def get_prime(n):
    
    result = [0]*(n+1)

    for i in range(2,n+1):
        
        if result[i] == 0:
            
            for j in range(i,n+1,i):
                
                result[j] += 1
    
    return result

 

 

에라토스테네스의 체를 약간 변형시킨 것이다.

 

result = [1]*(n+1)로 해서... 2부터 int(n**(1/2))까지 순회하는데... result[i] = 1이면

 

result에서 i보다 큰 i의 배수를 지우고 i가 소수라고 판정하는 거잖아.

 

반대로 result = [0]*(n+1)로 해서 2부터 n까지 순회하는데 result[i] = 0이면...

 

i는 소수이고 i 이상 i의 배수는 i를 소인수로 가지니까

 

 

여기서 2부터 int(n**(1/2))까지가 아니라 2부터 n까지 하는 이유는???

 

int(n**(1/2))보다 크고 n보다 작은 어떤 소수 p가 있을 수 있고... 그런 p에 대해서는 result[p] = 1이어야하는데,

 

int(n**(1/2))까지만 순회하면 result[p] = 0으로 체크가 안되거든

 

----------------------------------------------------------------------------------------------------------------------

 

여기까지 하면 모든 정수 2부터 10000000까지에 대하여 각 정수가 가지는 유일한 소인수의 개수를 구했다.

 

그러면 그 개수가 홀수인 정수와 짝수인 정수로 구분해야한다.

 

odd = [0]*(10**7+1)
even = [0]*(10**7+1)

for i in range(2,10**7+1):
    
    if counting[i] % 2 == 1:
        
        odd[i] = 1
    
    else:
        
        even[i] = 1

for i in range(2,10**7+1):
    
    odd[i] += odd[i-1]
    even[i] += even[i-1]

 

 

그리고 구간 쿼리로 주어지니 미리 prefix sum을 구해둔다

 

n = int(stdin.readline())

for _ in range(n):
    
    a,b = map(int,stdin.readline().split())

    x = odd[b] - odd[a-1]
    y = even[b] - even[a-1]

    print(y-x)