백준 27875번 - 파이파이

백준 27875번 문제 링크
문제 이름 : 파이파이
주 언어 : Python
태그 :
solved.ac 등급 : Diamond III (2023/03/20 확인)

문제 보기

문제 :

$\pi$로 나타내는 원주율은 원의 지름에 대한 둘레의 비율이다.
$\pi$의 값은 $3.1415926535897\cdots$와 같이 유리수가 아닌 무한소수이다.
그런데 $16$진법 세상에서의 $\pi$의 값은 $3.1415\cdots$가 아니다!
예를 들어, $16$진법 세상에서 $$\pi = 3 + \frac{2}{16^1} + \frac{4}{16^2} + \frac{3}{16^3} + \frac{15}{16^4} + \frac{6}{16^5}\cdots$$이기 때문에, $3.243\mathrm{F}6\cdots$와 같이 나타낸다.
하지만 $\pi$의 소수점 아래 $n$번째 자리의 숫자를 구하는 것은 매우 쉬운 일이기 때문에 $\pi^2$의 소수점 아래 $n$번째 자리의 숫자를 구해야 한다.
양의 정수 $n$이 주어지면, $16$진법 세상에서 $\pi^2$의 소수점 아래 $n$번째 자리의 숫자를 구해보자.
단, $16$진법 세상에서는 $10$ 이상의 숫자의 경우, 다음과 같이 알파벳 대문자를 이용하여 숫자를 표시한다.
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15

입력 :

첫째 줄에 $n$이 주어진다. $(1\le n \le 314\,159)$ 

출력 :

첫째 줄에 $16$진법 세상에서 $\pi^2$의 소수점 아래 $n$번째 자리의 숫자를 출력한다.


참고자료 1
이 문제는 풀었으나, 풀이를 쓰는 중입니다.
BBP 공식과 스피곳 알고리즘을 통해 한 자리수를 뽑아낼 수 있습니다.
제가 푼 방식보다 더 쉬운 방식이 있으나, 우선 제가 푼 방식은...
$$ {\pi}^{2} = \frac{9}{8} \sum_{k = 0}^{\infty} \frac{1}{{64}^{k}} \left(\frac{16}{{(6k + 1)}^{2}} - \frac{24}{{(6k + 2)}^{2}} - \frac{8}{{(6k + 3)}^{2}} - \frac{6}{{(6k + 4)}^{2}} + \frac{1}{{(6k + 5)}^{2}} \right) $$ 이 공식을 우선 증명 없이 가져와줍니다.
우리가 원하는걸 또 다르게 쓰면 다음과 같습니다.

$0 \leq S_{k} < 16$인 정수 $S_{k}$에 대하여 $$ {\pi}^{2} = \sum_{k = 0}^{\infty} \frac{S_{k}}{{16}^{k}} $$ 일 때, $S_{n}$의 값
즉, $S_{k}$는 ${\pi}^{2}$의 16진법 전개 방법입니다.
또, 위의 증명 없는 공식에서 ${\pi}^{2}$를 다음과 같이 표기해줍니다.
$$ {\pi}^{2} = \sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{18}{{(12k + 1)}^{2}} - \frac{27}{{(12k + 2)}^{2}} - \frac{1}{{(4k + 1)}^{2}} - \frac{27}{{4(12k + 4)}^{2}} + \frac{9}{{8(12k + 5)}^{2}} + \\ \frac{9}{{32(12k + 7)}^{2}} - \frac{27}{{64(12k + 8)}^{2}} - \frac{1}{{64(4k + 3)}^{2}} - \frac{27}{{256(12k + 10)}^{2}} + \frac{9}{{512(12k + 11)}^{2}} \right) $$
해당 공식 증명

우선 위의 증명 없는 공식을 참으로 받아들이고, $k := 2k$, $k := 2k + 1$로 쪼개어서 합쳐줍니다. (즉, 짝수항과 홀수항을 따로 생각함)
$$ {\pi}^{2} = \frac{9}{8} \left(\sum_{k = 0}^{\infty} \frac{1}{{64}^{2k}} \left(\frac{16}{{(12k + 1)}^{2}} - \frac{24}{{(12k + 2)}^{2}} - \frac{8}{{(12k + 3)}^{2}} - \frac{6}{{(12k + 4)}^{2}} + \frac{1}{{(12k + 5)}^{2}} \right) + \\ \sum_{k = 0}^{\infty} \frac{1}{{64}^{2k + 1}} \left(\frac{16}{{(12k + 7)}^{2}} - \frac{24}{{(12k + 8)}^{2}} - \frac{8}{{(12k + 9)}^{2}} - \frac{6}{{(12k + 10)}^{2}} + \frac{1}{{(12k + 11)}^{2}} \right)\right) $$ ${64}^{2k}$, ${64}^{2k + 1}$을 풀어써줍니다.
$$ {\pi}^{2} = \frac{9}{8} \left(\sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{16}{{(12k + 1)}^{2}} - \frac{24}{{(12k + 2)}^{2}} - \frac{8}{{(12k + 3)}^{2}} - \frac{6}{{(12k + 4)}^{2}} + \frac{1}{{(12k + 5)}^{2}} \right) + \\ \sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{16}{{64(12k + 7)}^{2}} - \frac{24}{{64(12k + 8)}^{2}} - \frac{8}{{64(12k + 9)}^{2}} - \frac{6}{{64(12k + 10)}^{2}} + \frac{1}{{64(12k + 11)}^{2}} \right)\right) $$ 굳이 시그마를 두개로 분리할 필요는 이제 없어졌으니 잘 합쳐줄 수 있습니다.
$$ {\pi}^{2} = \frac{9}{8} \left(\sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{16}{{(12k + 1)}^{2}} - \frac{24}{{(12k + 2)}^{2}} - \frac{8}{{(12k + 3)}^{2}} - \frac{6}{{(12k + 4)}^{2}} + \frac{1}{{(12k + 5)}^{2}} + \\ \frac{16}{{64(12k + 7)}^{2}} - \frac{24}{{64(12k + 8)}^{2}} - \frac{8}{{64(12k + 9)}^{2}} - \frac{6}{{64(12k + 10)}^{2}} + \frac{1}{{64(12k + 11)}^{2}} \right)\right) $$ 기분 나쁘게 생긴 $\frac{9}{8}$을 각 항에 녹여줍니다.
$$ {\pi}^{2} = \left(\sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{18}{{(12k + 1)}^{2}} - \frac{27}{{(12k + 2)}^{2}} - \frac{9}{{(12k + 3)}^{2}} - \frac{27}{{4(12k + 4)}^{2}} + \frac{9}{{8(12k + 5)}^{2}} + \\ \frac{18}{{64(12k + 7)}^{2}} - \frac{27}{{64(12k + 8)}^{2}} - \frac{9}{{64(12k + 9)}^{2}} - \frac{27}{{256(12k + 10)}^{2}} + \frac{9}{{512(12k + 11)}^{2}} \right)\right) $$ 약분 되는 친구는 약분 해줍니다.
$$ {\pi}^{2} = \left(\sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{18}{{(12k + 1)}^{2}} - \frac{27}{{(12k + 2)}^{2}} - \frac{1}{{(4k + 1)}^{2}} - \frac{27}{{4(12k + 4)}^{2}} + \frac{9}{{8(12k + 5)}^{2}} + \\ \frac{9}{{32(12k + 7)}^{2}} - \frac{27}{{64(12k + 8)}^{2}} - \frac{1}{{64(4k + 3)}^{2}} - \frac{27}{{256(12k + 10)}^{2}} + \frac{9}{{512(12k + 11)}^{2}} \right)\right) $$

$T_{k}$을 도입해줍니다.
$T_{0} = S_{0}$, $T_{k} = 256 S_{3k - 2} + 16 S_{3k - 1} + S_{3k}$이라 하면, $0 \leq T_{k} < 4096$인 정수 $T_{k}$에 대하여 $$ {\pi}^{2} = \sum_{k = 0}^{\infty} \frac{T_{k}}{{4096}^{k}} $$ 이 된다.
즉, $T_{k}$는 ${\pi}^{2}$의 4096진법 (???) 전개 방법입니다.
그러면 다음의 식이 성립하게 됩니다.
$$ \sum_{k = 0}^{\infty} \frac{T_{k}}{{4096}^{k}} = \sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left(\frac{18}{{(12k + 1)}^{2}} - \frac{27}{{(12k + 2)}^{2}} - \frac{1}{{(4k + 1)}^{2}} - \frac{27}{{4(12k + 4)}^{2}} + \frac{9}{{8(12k + 5)}^{2}} + \\ \frac{9}{{32(12k + 7)}^{2}} - \frac{27}{{64(12k + 8)}^{2}} - \frac{1}{{64(4k + 3)}^{2}} - \frac{27}{{256(12k + 10)}^{2}} + \frac{9}{{512(12k + 11)}^{2}} \right) $$ 오른쪽 식이 너무 과도하게 기니까, 이를 적당한 두 다항식의 비 $\frac{a(k)}{b(k)}$라고 퉁치면
$$ \sum_{k = 0}^{\infty} \frac{T_{k}}{{4096}^{k}} = \sum_{k = 0}^{\infty} \frac{1}{{4096}^{k}} \left( \frac{a(k)}{b(k)} \right) $$ 가 됩니다.
잠깐 문제를 바꾸어서, $S_{n}$을 구하는 문제가 아니라 $T_{N}$을 구하는 문제라고 생각해보겠습니다.
Spigot 알고리즘의 아이디어에서, 양 변에 $4096^{N}$을 곱해줍니다.
$$ \sum_{k = 0}^{\infty} \frac{T_{k}}{{4096}^{k - N}} = \sum_{k = 0}^{\infty} \frac{1}{{4096}^{k - N}} \left( \frac{a(k)}{b(k)} \right) $$ 잠시 좌변만 보도록 하겠습니다.
$$ \sum_{k = 0}^{\infty} \frac{T_{k}}{{4096}^{k - N}} = \left( \sum_{k = 0}^{N - 1} \frac{T_{k}}{{4096}^{k - N}} \right) + \frac{T_{N}}{{4096}^{N - N}} + \left( \sum_{k = N + 1}^{\infty} \frac{T_{k}}{{4096}^{k - N}} \right) \\ = \left( \sum_{k = 0}^{N - 1} T_{k} {(4096)}^{N - k} \right) + T_{N} + \left( \sum_{k = N + 1}^{\infty} \frac{T_{k}}{{4096}^{k - N}} \right) $$ $\left( \sum_{k = 0}^{N - 1} T_{k} {(4096)}^{N - k} \right)$은 $4096$보다 크(거나 아예 0이어서 상관할 필요가 없)고, $\left( \sum_{k = N + 1}^{\infty} \frac{T_{k}}{{4096}^{k - N}} \right)$은 기껏 해야 $0$보다 크고 $1$보다 작습니다. ($N < k$일 때 $T_{k} = 4095$여야만 $1$의 값을 가짐, 그렇다면 ${\pi}^{2}$가 무리수 라는 것에 모순)
즉, 해당 식을 어떻게든 계산할 수 있다고 치면, $4096$보다 큰 부분은 계속 쳐내고, 마지막에 소수점을 절삭해주면 $T_{N}$의 값을 구할 수 있는 셈입니다.
이제 다시 우변을 보겠습니다.
$$ \sum_{k = 0}^{\infty} \frac{1}{{4096}^{k - N}} \left( \frac{a(k)}{b(k)} \right) = \sum_{k = 0}^{N} \frac{1}{{4096}^{k - N}} \left( \frac{a(k)}{b(k)} \right) + \sum_{k = N + 1}^{\infty} \frac{1}{{4096}^{k - N}} \left( \frac{a(k)}{b(k)} \right) \\ = \sum_{k = 0}^{N} {(4096)}^{N - k} \left( \frac{a(k)}{b(k)} \right) + \sum_{k = N + 1}^{\infty} \frac{1}{{4096}^{k - N}} \left( \frac{a(k)}{b(k)} \right) $$ 오른쪽 항 $\sum_{k = N + 1}^{\infty} \frac{1}{{4096}^{k - N}} \left( \frac{a(k)}{b(k)} \right)$은 충분히 큰 $N$에 대해 $0$과 $1$ 사이의 값을 가지게 될 것입니다. ($a/b$가 양수이고 꽤 작다는 가정하에...)
그렇다면 왼쪽 항인 $$ \sum_{k = 0}^{N} {(4096)}^{N - k} \left( \frac{a(k)}{b(k)} \right) = \sum_{k = 0}^{N} \left( \frac{{(4096)}^{N - k} a(k)}{b(k)} \right) $$ 을 4096으로 나눈 나머지 (즉, 4096으로 뺄 수 있을 때까지 빼고 남은 양의 실수)를 알고 싶다면 모듈러 연산을 도입해주면 됩니다. $$ \sum_{k = 0}^{N} \left( \frac{{(4096)}^{N - k} a(k) \pmod{4096 \times b(k)}}{b(k)} \right) $$ 이런 이상한 문제를 찾아푸시는 분이라면 $a^{n} \pmod{c}$를 $\log(n)$ 시간에 구하는 빠른 거듭제곱 방법은 아실거라고 믿습니다.

(이 후 작성 중, ${(4096)}^{N - k} a(k) \pmod{4096 \times b(k)}$의 값은 정수로 구하고 그걸 $b(k)$로 나누어서 실수형 변수로 만들고 다 더해주면 OK, $b(k)$는 위에서 표기한 $\frac{1}{{4096}^{k}}$에 곱해진 10개의 식을 각자 생각하고 $b(k)$ 10개에 대해 계산한 값을 더해줌, $T_{n}$에서 $S_{n}$도 구할 수 있음.)

-번째 푼 문제 (2023/03/--)
처음 푼 Diamond III 문제