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

1. 문제

 

15712번: 등비수열 (acmicpc.net)

15712번: 등비수열

 

초항이 a, 공비가 r, 항 수가 n인 등비수열의 합을 mod로 나눈 나머지를 구하는 간단한 문제

 

초항이 a이고 공비가 r이며 항 수가 n인 등비수열의 합은.. 공비 r이 1이 아니면,

 

$$S = a \times \frac{r^{n}-1}{r-1}$$

 

이라는 아주 쉬운 공식이 있고 이거에 따라 계산해서 mod로 나눈 나머지 구하면 되는거 아니냐

 

라고 쉽게 생각하면 이 문제는 풀수가 없다

 

a,r,n이 작으면 상관 없겠지만... 매우 크면 $r^{n}$을 계산을 못한다

 

그러면 뭐 modular exponentiation으로 나머지로 거듭제곱하면 되는거 아니냐.. 하지만 r-1 나눗셈이 있어서..

 

잘 알겠지만 모듈로 연산에서 나눗셈은 일반적으로 성립하지 않는다

 

모듈로 연산의 역원을 구하면 되는거 아니냐.. 당연하지만 r과 mod가 서로소가 아니면 존재하지 않는다

 

 

2. 기하급수의 점화식

 

다음과 같은 기하급수 $$1+r+r^{2}+r^{3}+...+r^{n}$$에 대해 생각해보자.

 

n = 0이면 $1$

 

n = 1이면 $1+r$

 

n = 2이면 $1+r+r^{2}$

 

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

 

n = 3부터 홀수만 자세히 살펴보면..

 

$$1+r+r^{2}+r^{3} = 1+r + (1+r)r^{2} = (1+r) \times (1+r^{2})$$

 

n = 5이면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5} = (1+r) \times (1+r^{2} + r^{4})$$

 

n = 7이면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5}+r^{6}+r^{7} = (1+r) \times (1+r^{2} + r^{4} + r^{6})$$

 

규칙이 보이는가?

 

쉽게 생각해서.. 2개 항씩 묶어보면.. (1+r)이 공통인수로 있고, 각각은 1, $r^{2}$, $r^{4}$, $r^{6}$,... 씩 곱한 값을 더하면 된다.

 

n = 2k+1로 홀수라면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5}+...+r^{2k}+r^{2k+1} = (1+r) \times (1+r^{2}+r^{4}+...+r^{2k})$$

 

수학적 귀납법으로 모든 음이 아닌 정수 k=0,1,2,...에 대해 성립한다는 것은 쉽게 증명할 수 있다.

 

k=0에서는 위에서 n=1일때 1+r임을 보였고

 

n=2k+1에서 위 식이 성립한다고 하면... n=2k+3에서 보이면 된다.

 

n = 2k+3이면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5}+...+r^{2k}+r^{2k+1}+r^{2k+2}+r^{2k+3}$$

 

여기서.. $$r^{2k+2}+r^{2k+3} = (1+r)r^{2k+2}$$이므로..

 

이걸 1+r로 묶으면 뭐..

 

$$(1+r) \times (1+r^{2}+r^{4}+...+r^{2k}+r^{2k+2})$$

 

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

 

이번엔 짝수에 대해서 알아보자.

 

n = 0이면 $1$

 

n = 2이면 $1+r+r^{2}$

 

n = 4부터 자세히 살펴보면..

 

$$1+r+r^{2}+r^{3}+r^{4} = 1 + r + r^{2} + (r+r^{2})r^{2} = 1 + (r+r^{2})(1+r^{2})$$

 

n = 6이면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5}+r^{6} = 1 + r + r^{2} + (r+r^{2})r^{2} + (r+r^{2})r^{4}) = 1+(r+r^{2})(1+r^{2}+r^{4})$$

 

n = 8 이면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5}+r^{6}+r^{7}+r^{8} = 1+(r+r^{2})(1+r^{2}+r^{4}+r^{6})$$

 

벌써 규칙이 보이는가??

 

n = 2k라면..

 

$$1+r+r^{2}+r^{3}+r^{4}+...+r^{2k-1}+r^{2k} = 1+(r+r^{2})(1+r^{2}+r^{4}+...+r^{2(k-1)})$$

 

수학적 귀납법으로 역시 쉽게 증명 가능하다.

 

모든 자연수 k=1,2,...에 대하여..

 

k = 1이면.. $1+r+r^{2}$인 것은 자명하고

 

n=2k에서 성립한다고 가정하고, n=2k+2에서 성립함을 보인다.

 

$$1+r+r^{2}+r^{3}+r^{4}+...+r^{2k-1}+r^{2k}+r^{2k+1}+r^{2k+2}$$에서..

 

$$r^{2k+1}+r^{2k+2} = (r+r^{2})r^{2k}$$니까...

 

$$1+r+r^{2}+r^{3}+r^{4}+...+r^{2k-1}+r^{2k}+r^{2k+1}+r^{2k+2} = 1+(r+r^{2})(1+r^{2}+r^{4}+...+r^{2(k-1)}+r^{2k})$$

 

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

 

3. 파이썬 구현 예시

 

알고리즘을 정리하면 다음과 같게 된다.

 

$$G(r,n) = 1+r+r^{2}+r^{3}+...+r^{n}$$을 구하려면...

 

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

 

 

3-2) n = 2k+1로 홀수라면..

 

$$1+r+r^{2}+r^{3}+r^{4}+r^{5}+...+r^{2k}+r^{2k+1} = (1+r) \times (1+r^{2}+r^{4}+...+r^{2k})$$

 

여기서 $1+r^{2}+r^{4}+...+r^{2k}$은 자세히 살펴보면.. r 대신에 $r^{2}$을 넣은 기하급수와 마찬가지다.

 

$$1+r^{2}+r^{4}+...+r^{2k} = 1+(r^{2})^{1} + (r^{2})^{2} +... +(r^{2})^{k}$$

 

k는 어떻게 구해??

 

아주 간단하다. n=2k+1이니까.. n-1 = 2k이고... 그러면 (n-1)/2 = k잖아

 

그래서... $$1+r+r^{2}+r^{3}+r^{4}+r^{5}+...+r^{2k}+r^{2k+1} = (1+r) \times (1+r^{2}+r^{4}+...+r^{2k})$$은 다음과 같이 바꿔 쓸 수 있다.

 

$$G(r,n) = (1+r) \times G(r^{2}, (n-1)/2)$$

 

 

3-3) n = 2k로 짝수라면..

 

$$1+r+r^{2}+r^{3}+r^{4}+...+r^{2k-1}+r^{2k} = 1+(r+r^{2})(1+r^{2}+r^{4}+...+r^{2(k-1)})$$

 

마찬가지로.. 

 

$$1+r^{2}+r^{4}+...+r^{2(k-1)} = 1+(r^{2})^{1} + (r^{2})^{2} +... +(r^{2})^{k-1}$$

 

이고... n = 2k이면.. k-1 = (n-2)/2니까..

 

$$1+r+r^{2}+r^{3}+r^{4}+...+r^{2k-1}+r^{2k} = 1+(r+r^{2})(1+r^{2}+r^{4}+...+r^{2(k-1)})$$은 다음과 같이 바꿔쓸 수 있다.

 

$$G(r,n) = 1 + (r+r^{2}) \times G(r^{2}, (n-2)/2)$$

 

이 결과를 재귀함수로 다음과 같이 나타낼 수 있을 것이다.

 

#기하급수의 합

#r은 공비, n은 마지막 항의 지수(항 수-1)
def geometric(r,n):
    
    if n == 0:
        
        return 1
    
    else:
        
        #n이 홀수
        #g(r,n) = (1+r)g(r**2,(n-1)/2)
        
        if n % 2 == 1:
            
            return (1+r)*geometric(r*r, (n-1)//2)
        
        #n이 짝수
        #g(r,n) = 1+(r+r**2)g(r**2,(n-2)/2)
        
        else:
            
            return 1 + (r+r*r)*geometric(r*r, (n-2)//2)

 

하지만... 이렇게 구하면.. r과 n이 매우 클때 당연히 계산이 느려진다.

 

그러니까 이 값을 mod로 나눈 나머지를 요구하는 것이다.

 

#기하급수의 합

#r은 공비, n은 마지막 항의 지수(항 수-1), mod는 나머지 연산
def geometric(r,n,mod):
    
    if n == 0:
        
        return 1
    
    else:
        
        #n이 홀수
        #g(r,n) = (1+r)g(r**2,(n-1)/2)
        
        if n % 2 == 1:
            
            return ((1+r)%mod*geometric(r*r%mod, (n-1)//2, mod))%mod
        
        #n이 짝수
        #g(r,n) = 1+(r+r**2)g(r**2,(n-2)/2)
        
        else:
            
            return 1 + ((r+r*r)%mod*geometric(r*r%mod, (n-2)//2,mod))%mod

 

4. 풀이

 

초항이 a, 공비가 r, 항 수가 n인 등비급수의 합은

 

$$a + ar + ar^{2} + ... + ar^{n-1} = a(1+r+r^{2}+...+r^{n-1})$$이다.

 

위에서 구한 기하급수 점화식에 a를 곱하고, mod로 나눈 나머지를 구하면 되겠다.

 

from sys import stdin

def geometric(r,n,mod):
    
    if n == 0:
        
        return 1
    
    else:
    
        if n % 2 == 1:
            
            return ((1+r)%mod*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

a,r,n,mod = map(int,stdin.readline().split())

print((a%mod)*geometric(r,n-1,mod)%mod)

 

 

참조

 

 

algorithm - Geometric Series Modulus operation - Stack Overflow

Geometric Series Modulus operation