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

1. 약수의 개수

 

자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$라고 한다면,

 

n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$

 

n을 소인수분해하여, 소인수들의 지수 + 1의 곱의 합이 약수의 개수이다.

 

 

1-1) 간단한 증명

 

왜냐하면 n의 약수는 $p_{1}, p_{2}, ... , p_{k}$들의 곱으로 이루어져 있는데, 각각은 $x_{1}, x_{2}, ... , x_{k}$개씩 사용할 수 있다.

 

따라서 곱의 법칙에 의해 모든 경우의 수는 $p_{1}, p_{2}, ... , p_{k}$을 각각 (0,1,2,...,$x_{1}$), (0,1,2,...,$x_{2}$), ... , (0,1,2,...,$x_{k}$)번씩 사용할 수 있어서..

 

$$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$

 

 

1-2) 성질

 

제곱수의 약수의 개수는 홀수개이고, 그렇지 않은 수는 짝수개이다.

 

반대로 약수의 개수가 홀수개이면 제곱수이고 짝수개이면 제곱수가 아니다.

 

 

1-3) 간단한 증명

 

홀수의 곱은 홀수

 

홀수와 짝수의 곱은 짝수

 

짝수의 곱은 짝수이다.

 

먼저, n이 어떤 수 m의 제곱으로 나타난다면, n의 소인수분해가 $$n = m^{2} = (p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}})^{2} = p_{1}^{2x_{1}}p_{2}^{2x_{2}}...p_{k}^{2x_{k}}$$

 

따라서, $$d(n) = (2x_{1}+1)(2x_{2}+1)...(2x_{k}+1)$$이므로, 제곱수의 약수의 개수가 홀수들의 곱으로 구해진다.

 

홀수의 곱은 홀수이므로, 제곱수의 약수의 개수는 홀수개이다.

 

역으로 $d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$이 홀수라면, 모든 $x_{1}+1, x_{2}+1, ... , x_{k}+1$이 모두 홀수라는 뜻이다.

 

그러므로 $x_{1}, x_{2}, ... , x_{k}$은 모두 짝수이고, 그래서 n은 어떤 수의 제곱으로 나타낼 수 있다.

 

반면 n이 제곱수가 아니라면, $x_{1}, x_{2}, ... , x_{k}$이 홀수인 경우가 존재하여, $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$에서 짝수와 홀수들의 곱으로 이루어진다.

 

홀수와 짝수의 곱은 짝수이다. 따라서 제곱수가 아닌 수의 약수의 개수는 짝수개이다.

 

역으로 $d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$이 짝수라면, $x_{1}+1, x_{2}+1, ... , x_{k}+1$에서 적어도 하나는 짝수이다.

 

그러므로 $x_{1}, x_{2}, ... , x_{k}$에 적어도 하나가 홀수가 있으므로, n은 어떤 수의 제곱으로 나타낼 수 없다.

 

 

2. 연습문제

 

코딩테스트 연습 - 약수의 개수와 덧셈 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

주어진 left와 right 사이에서 약수의 개수가 짝수인 수는 더하고, 홀수인 수는 뺀 값을 구하는 문제

 

 

3. 풀이

 

소인수분해를 이용해서 소인수들의 지수를 구하고, 지수+1의 곱으로 약수의 개수를 구한다음에, 짝수인지 홀수인지 판단

 

def solution(left, right):
    
    answer = 0
    
    for n in range(left,right+1):
        
        #변수에 원본 n을 복사
       
        number = n
        
        #n에 대한 소인수분해
        p = 2
        
        divisor = 1
        
        while p*p <= n:
            
            count = 0
            
            if n % p == 0:
                
                while n % p == 0:
                    
                    n = n // p
                    
                    count += 1
                
                #p의 지수+1을 divisor에 누적 곱
                divisor *= (count+1)
            
            p = p + 1
        
        if n > 1:
            
            #n>1이면 n도 소인수이므로, 2를 곱해준다
            divisor *= 2
        
        #약수의 개수가 짝수이면 더해주고, 아니면 빼주고
        if divisor % 2 == 0:
            
            answer += number
        
        else:
            
            answer -= number
    
    return answer

 

약수의 개수의 성질을 이용해서, 제곱수인지 아닌지를 판단

 

제곱수이면 약수의 개수가 홀수이므로 빼주고, 제곱수가 아니라면 약수의 개수가 짝수이므로 더해준다.

 

#제곱수의 약수의 개수는 홀수개이고, 
#제곱수가 아닌 수의 약수의 개수는 짝수개
def solution(left, right):
    
    answer = 0
    
    for n in range(left,right+1):
        
        #n이 제곱수라면, (1/2)제곱을 하더라도, 정수이므로
        if int(n**(1/2)) == n**(1/2):
            
            answer -= n
        
        else:

            answer += n
    
    return answer

 

 

4. 약수의 합

 

자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$이라고 하자.

 

그러면, n의 모든 약수의 합은..

 

$p_{i}$가 곱에 사용할 수 있는 경우가 0, 1, 2, ... , $x_{i}$번 사용할 수 있어서

 

모든 $i = 1,2,3,...,k$에 대하여, $(1+p_{i}+p_{i}^{2}+p_{i}^{3}+...+p_{i}^{x_{i}})$의 곱으로 가능한 모든 약수들의 합을 얻을 수 있다.

 

$$\sigma(n) = \prod_{i=1}^{k}(1+p_{i}+p_{i}^{2}+...+p_{i}^{x_{i}})$$

 

그런데, $(1+p_{i}+p_{i}^{2}+p_{i}^{3}+...+p_{i}^{x_{i}})$은 초항이 1이고 항 수가 $x_{i}+1$개이며 공비가 $p_{i}$인 등비수열의 합이다.

 

즉,  $$(1+p_{i}+p_{i}^{2}+p_{i}^{3}+...+p_{i}^{x_{i}}) = \frac{p_{i}^{x_{i}+1}-1}{p_{i}-1}$$

 

그러므로, n의 약수의 합은..

 

$$\sigma(n) = \prod_{i=1}^{k} \frac{p_{i}^{x_{i}+1}-1}{p_{i}-1}$$

 

즉 n을 소인수분해해서, n의 소인수 $p_{i}$와 지수 $x_{i}$만 안다면, 약수의 합을 구할 수 있다.

 

 

5. 연습문제

 

11693번: n^m의 약수의 합 (acmicpc.net)

11693번: n^m의 약수의 합

 

n,m이 주어질때, $n^{m}$의 약수의 합을 구하는 문제

 

 

6. 풀이

 

약수의 합의 공식을 이용하자.

 

n을 소인수분해하면, $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$으로 구할 수 있을 것이다.

 

그러면, $n^{m}$은...

 

$$n^{m} = p_{1}^{mx_{1}}p_{2}^{mx_{2}}...p_{k}^{mx_{k}}$$

 

그러므로, $n^{m}$의 약수의 합은...

 

$$\sigma(n^{m}) = \prod_{i=1}^{k} \frac{p_{i}^{mx_{i}+1}-1}{p_{i}-1}$$

 

그러므로 n을 소인수분해해서 소인수와 지수를 구하는게 먼저다.

 

그리고 각 소인수의 지수에 m배를 해준다.

 

n,m = map(int,stdin.readline().split())

mod = 1000000007

prime = []

p = 2

while p*p <= n:
    
    if n % p == 0:
        
        count = 0

        while n % p == 0:
            
            n = n//p

            count += 1
        
        prime.append((p,count*m))
    
    p = p + 1

if n > 1:
    
    prime.append((n,m))

 

다음에 약수의 합을 구하기 위해서는...

 

$p_{i}^{mx_{i}+1}$을 구해야하는데 이미 알다시피 $p_{i}$, $x_{i}$, m이 너무 크면 구하는데 시간이 너무 오래걸린다.

 

이를 위해 이미 등비수열의 합을 구하는 방법에 대해 공부했었다.

 

컴퓨터가 등비수열의 합을 구하는 방법 (tistory.com)

컴퓨터가 등비수열의 합을 구하는 방법

 

기하급수의 점화식을 이용해서 등비수열의 합을 아주 빠르게 구하자.

 

공비가 r이고 항 수가 n+1인 등비수열의 합을 구할려면..

 

$$G(r,n) = 1 + r + r^{2} + ... + r^{n}$$

 

n = 0이면, $$G(r,0) = 1$$

 

n이 홀수이면, $$G(r,n) = (1+r)G(r^{2},(n-1)/2)$$

 

n이 짝수이면, $$G(r,n) = 1+(r+r^{2})G(r^{2},(n-2)/2)$$

 

r이 너무 크면 오래걸리기 때문에 곱하면서 mod = 1000000007로 나누면서 곱해준다.

 

def geometric(r,n,mod):

    if n == 0:
        
        return 1
    
    else:

        if n % 2 == 1:
            
            return ((1+r)*geometric(r*r%mod,(n-1)//2,mod))%mod
        
        elif n % 2 == 0:
            
            return 1+((r+r*r)%mod*geometric(r*r%mod,(n-2)//2,mod))%mod

 

그러면 등비수열의 합도 구할 수 있고, 소인수분해로 소인수와 지수도 구했으니까... 

 

from sys import stdin

#1+r+r**2+...+r**n의 합
def geometric(r,n,mod):

    if n == 0:
        
        return 1
    
    else:

        if n % 2 == 1:
            
            return ((1+r)*geometric(r*r%mod,(n-1)//2,mod))%mod
        
        elif n % 2 == 0:
            
            return 1+((r+r*r)%mod*geometric(r*r%mod,(n-2)//2,mod))%mod

n,m = map(int,stdin.readline().split())

mod = 1000000007

#n에 대한 소인수분해

prime = []

p = 2

while p*p <= n:
    
    if n % p == 0:
        
        count = 0

        while n % p == 0:
            
            n = n//p

            count += 1
        
        prime.append((p,count*m))
    
    p = p + 1

if n > 1:
    
    prime.append((n,m))

answer = 1

#약수의 합
#초항이 1이고, 항 수가 count+1이고 공비가 소인수 p인 등비수열의 합의 곱이 약수의 합

for p,count in prime:
    
    answer *= geometric(p,count,mod)

    answer %= mod

print(answer)