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

1. 문제

 

17427번: 약수의 합 2 (acmicpc.net)

17427번: 약수의 합 2

 

2. 풀이

 

문제를 요약하면 1부터 n까지 각각 약수의 합을 전부 더한 값을 출력하는 문제

 

시간이 0.5초라서 당연히 1부터 n까지 소인수분해하고 약수의 합을 구한다면 시간초과겠지

 

약수의 합을 구하는 공식은...

 

https://deepdata.tistory.com/588

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

 

0.5초라면 상당히 빠르게 구해야할 것 같은 느낌이 드는데

 

일단 smallest prime factor를 이용한다면 소인수분해를 조금 더 빠르게 할 수 있다

 

기억이 안나니 살짝 봐주고

 

https://deepdata.tistory.com/604

소인수분해 심화응용 - linear sieve와 smallest prime factor 알고리즘 익히기

 

def get_spf(n):
    
    #각 수의 spf는 i가 되도록 초기화
    spf = [i for i in range(n+1)]
    
    #모든 짝수는 2를 소인수로 가진다.
    for i in range(4,n+1,2):
        
        spf[i] = 2
    
    #3부터 n**(1/2)까지 spf를 계산
    for i in range(3,int((n+1)**(1/2))+1):
        
        #i의 가장 작은 소인수가 i라는 것은
        #i가 소수이고..
        if spf[i] == i:
            
            #i를 제외한 i의 배수는 i로 나누어 떨어지고
            for j in range(i*i, n+1, i):
                
                #아직 j의 spf가 계산되지 않았다면..
                if spf[j] == j:
                    
                    #i의 배수인 j는 spf가 i이다.
                    spf[j] = i
    
    return spf

 

이를 이용해서 소인수분해를 수행한다.

 

그런데 약수의 합을 구해야하므로...

 

소인수랑 해당 소인수의 지수까지 구해서.. 등비수열 공식으로 한번에 구해줘야한다

 

def factorization(n,spf):
    
    summation = {}

    answer = 1

    while n != 1:
        
        summation[spf[n]] = summation.get(spf[n],0) + 1

        n = n//spf[n]
    
    for a,b in summation.items():
        
        answer *= (a**(b+1)-1)//(a-1)

    return answer

 

소인수분해 할때마다, dictionary에 소인수랑 지수도 저장해두고

 

소인수분해가 끝나면, key,value를 순회해서 약수의 합을 한번에 구해준다

 

그러면 모든 준비가 끝났다

 

spf를 구해주고, 1부터 n까지 순회해서...

 

i가 1인 경우 spf[1] = 1이라서.. 1 더해주고 (1은 소수가 아니라 예외사항)

 

spf[i] == i인 경우 i는 소수이므로 i+1을 더해준다.. 소수 i의 약수는 1,i니까

 

그 외에는 소인수분해를 통해 약수의 합을 구해서 더해준다

 

n = int(stdin.readline())

spf = get_spf(n)

answer = 0

for i in range(1,n+1):
    
    if i == 1:
        
        answer += 1
    
    elif spf[i] == i:
        
        answer += (i+1)
    
    else:
        
        answer += factorization(i,spf)

print(answer)

 

 

3. 더블 카운팅(double counting)

 

어떠한 등식을 증명할 때, 양변의 의미가 같음을 밝혀서 식의 값도 서로 같다고 증명하는 방법

 

등식이 도저히 직접 증명하기 어려울때, 간접적으로 증명하는 방식으로 자주 사용

 

더블 카운팅 - 나무위키 (namu.wiki)

더블 카운팅 - 나무위키

 

4. 배수를 이용해 약수를 찾는 방법

 

예를 들어 1부터 10까지 각각 약수를 적어본다면 다음과 같다

 

 

 

 

그러면 놀라운 특징이 보이는데

 

1은 10개가 있다.

 

2는 5개, 3은 3개, 4는 2개, 5는 2개, 6,7,8,9,10은 1개

 

이는 10 이내에서 1의 배수가 10개있고

 

2의 배수는 5개 2,4,6,8,10가 있고

 

3의 배수는 3개 3,6,9가 있고..

 

4의 배수는 2개 4,8이 있고

 

5의 배수는 2개 5,10이 있고,...

 

6,7,8,9,10은 10 이내에서 배수가 1개 있고

 

따라서 1부터 n 이내에서 모든 약수들의 합은 각각의 약수를 찾는것이 아니라,

 

조금 다르게 생각해서 1부터 n 각각이 n이내에서 배수의 개수가 몇개인지 세면 아주 빠르게 찾을 수 있다.

 

배수의 개수는 어떻게 셀 수 있을까? 

 

구체적으로 n 이내에서 x의 배수의 개수는 몇개일까? n//x개이다.

 

10이내에서 2의 배수가 10//2 = 5로 5개

 

from sys import stdin

n = int(stdin.readline())

answer = 0

for i in range(1,n+1):
    
    answer += (i*(n//i))

print(answer)