[PE] Project Euler 97

프로젝트 오일러 97번은 앞에선 열심히 메르센 소수에 대한 설명을 하고, 그 다음엔 넌-메르센 소수 이야기를 하더니, 마지막에 가서는 '앞에 주어진 수의 마지막 10자리 수를 구하시오'라고 하는, 조금 김빠지는 문제다.

 

이 문제에서 계산해야 하는 수는 28433×2^7830457+1로, 2^7830457를 어떻게 빠르게 계산해내는지가 관건이다. 해당 숫자는 계속 계산하기엔 큰 숫자가 될 것이고, 어차피 우리에게 필요한 숫자는 마지막 10자리 수이며, 그렇기 때문에 계산을 하다가 11자리수가 넘어가면 마지막 10자리 숫자만 잘라서 계속 계산을 이어나가는 방법을 활용할 것이다.

 

그런데 그렇다고 해도 2^7830457의 마지막 10자리 수를 빨리 계산해내야 하는 문제가 남는다. 문제에 나이브하게 접근하면 이렇게 풀어도 무방하긴 하다.

x = 28433
for _ in range(7830457):
    x*=2
    x%=10**10
x+=1
print(x)

그리고 실제로 이렇게 계산을 돌리더라도 10^7번 이하로 루프를 돌며 계산하는 데에는 그리 오랜 시간이 걸리지 않는다.

 

하지만 분명 2를 7830457번 곱하는 것보다 2^7830457를 빨리 계산하는 방법이 있을 것이다. 좀 더 쉬운 문제로, 만약 우리가 2^16을 계산하고 싶으면 다음의 과정을 거치는 것이 2를 16번 곱하는 것보다 빠를 것이다.

- 2^2을 구하기 위해 2*2를 계산한다.

- 2^4을 구하기 위해 앞서 계산한 2^2을 두 번 곱한다.

- 2^8을 구하기 위해 앞서 계산한 2^4을 두 번 곱한다.

- 2^16을 구하기 위해 앞서 계산한 2^8을 두 번 곱한다.

이렇게 하면 4번의 연산만으로 2^16 값을 구할 수 있다. 즉, 앞서 계산한 숫자를 잘 활용하여 뒤의 계산을 하는 데에 쓰는 것이다.

 

위의 방법으로 일반적인 2^n꼴의 수를 빠르게 계산할 수는 없을까? 경우의 수를 둘로 나누어보자.

i) n이 짝수이면, 2^(2k)은 2^k을 두 번 곱하여 얻을 수 있다.

ii) n이 홀수이면, 2^(2k+1)은 2^k을 두 번 곱한 뒤 2를 곱하여 얻을 수 있다.

잘 생각해보면 이 과정은 n을 이진수로 만드는 과정과 비슷한것 같다. 예를 들어, 37이라는 숫자를 이진수로 바꾸려고 한다면,

- 37은 2로 나눠서 1이 남으므로, xx..xx1 꼴(마지막 자리수가 1)일 것이다.

- 그러면 37에서 1을 빼면 이 수는 xx..xx0 꼴이 된다. 이제 이 숫자를 2로 나누면 xx..xx만 남는다. (1)

- 36/2 = 18인데, 이 숫자는 2로 나눠서 0이 남으므로, xx..xx0꼴일 것이다. 2로 나누면 xx..xx만 남는다. (0)

- 18/2 = 9인데, 이 숫자는 2로 나눠서 1이 남으므로, xx..xx1꼴일 것이다. 1을 빼고 2로 나누면 xx..xx만 남는다. (1)

- 8/2 = 4인데, 이 숫자는 2로 나눠서 0이 남으므로, xx..xx0꼴일 것이다. 2로 나누면 xx..xx만 남는다. (0)

- 4/2 = 2인데, 이 숫자는 2로 나눠서 0이 남으므로, xx..xx0꼴일 것이다. 2로 나누면 xx..xx만 남는다. (0)

- 2/2 = 1인데, 이 숫자는 2로 나눠서 1이 남으므로, xx..xx1꼴일 것이다. 1을 빼고 2로 나누면 xx..xx만 남는다. (1)

- 0이 남았다. 과정 종료.

 

이렇게 이어진 계산을 가지고 역으로 생각하면,

- 처음에 1로 시작. (1, 1)

- 여기에 2를 곱한다. (2, 10)

- 여기에 2를 곱한다. (4, 100)

- 여기에 2를 곱하고 1을 더한다. (9, 1001)

- 여기에 2를 곱한다. (18, 10010)

- 여기에 2를 곱하고 1을 더한다. (37, 100101)

의 순서로 37을 이진수로 만들어낼 수 있다.

 

2^n을 빠르게 계산하기 위해 필요한 건 뒤에 설명한 역으로 과정을 거치는 방법이다. 앞선 예시에서 37을 이진수로 바꾸는 과정을 설명했는데, 2를 곱하는 것 대신 주어진 숫자를 두 번 곱하는 것, 2를 곱하고 1을 더하는 것 대신 주어진 숫자를 두 번 곱하고 2를 곱해주는 것으로 바꾸면 2^37도 빠르게 계산 가능하다. 

 

- 처음에 1로 시작. 끝 자리가 1이므로 2를 곱한다. (2^1, 1)

- 제곱한다. (2^2, 10)

- 제곱한다. (2^4, 100)

- 제곱하고 2를 곱한다. (2^9, 1001)

- 제곱한다. (2^18, 10010)

- 제곱하고 2를 곱한다. (2^37, 100101)

 

예시를 가지고 생각해보면, 37을 이진수로 바꾼 100101만 있으면, 제일 앞 자리부터 순차적으로 보면서 1일 경우 제곱 후 2 곱하기, 0일 경우 제곱을 하는 과정을 거치면 된다는 걸 알 수 있다. 이를 임의의 n에 대해서도 계산 가능하게 하려면 다음의 과정을 거치면 된다.

1) n을 이진수로 변환

2) 이진수의 제일 앞자리부터 순차적으로 체크하며 앞서 설명한 과정을 반복

 

그리고 이를 코드로 옮기면 다음과 같다.

b = str(bin(7830457)) # 0b11101110111101110111001
s = b[2:] # 11101110111101110111001
x=1
for i in s:
    x=x*x%10**10
    if int(i): # i가 1이면 True, 0이면 False 된다.
        x*=2
x=(x*28433+1)%10**10
print(x)

이렇게 하면 나이브한 코드가 시간이 O(n)만큼 걸릴때 O(log n)으로 단축시킬 수 있다.