[BOJ 16141] 정수론과 응용: 레시테이션

아주 교육적인 문제 xudyh's sieve를 잘 활용할 수 있냐를 묻고 있다.(아마 그럴거다)
xudyh's sieve를 유도하면서 어떻게 식을 변형할지 알아보자. 앞으로 어떤 함수의 1부터 $N$까지 부분합을 $S_{f}(N)$이라 적겠다. 위 테그닉은 $S_{f*g}(N)$과 $S_{g}(N)$을 쉽게 계산할 수 있을 때 $S_{f}(N)$을 쉽게 계산하는 방법에 대해 말해준다. 다음 식과 함께 시작하자.
\[S_{f*g}(N)=\sum_{d=1}^{N} g(d)S_{f}(\lfloor \frac{N}{d} \rfloor)\]
이때 적절한 변형을 통해 다음을 얻는다.
\[S_{f}(N) = \frac{1}{g(1)}(S_{f*g}(N) - \sum_{d=2}^{N} g(d)S_{f}(\lfloor \frac{N}{d} \rfloor))\]
자 이제 본 문제의 주어진 식을 변형해보자.
\[\sum_{i=1}^{n} \sum_{u=1}^{v} \phi(i,u)\]
이때 $\phi(n,k)$는 Jordan totient function이라고도 불리는데 다음을 만족한다.
\[\phi(n,k)=\sum_{d|n} \mu(d) \lfloor \frac{N}{d} \rfloor^{k}\]
다음을 정의하자.
\[H(n,k)=\sum_{i=1}^{k} n^{i}\]
구한 식들을 이용해 준식을 변형해보자. 
\[\sum_{i=1}^{n} \sum_{d|i} \mu(d) H(\lfloor \frac{i}{d} \rfloor, v)\]
이때 이렇게 쓰면 어떨까?
\[f(i) = \sum_{d|i} \mu(d) H(\lfloor \frac{i}{d}\rfloor, v)\]
\[s_{f}(n) = \sum_{i=1}^{n} f(i)\]
짜잔, 우리가 구하려는 식은 $f$의 부분합이 되어버렸다. 우린 $f=\mu * H$라는 것을 알 수 있고 이로써 $u*f=H$를 얻는다.($u*\mu = \mathbf{I}$) 앞서 유도한 xudyh's sieve에 대입해보자.
\[S_{f}(n) = S_{H}(n) - \sum_{d=2}^{n} dS_{f}(\lfloor \frac{n}{d} \rfloor))\]
세상에... 이것보다 간단할 수 있을까? 이제 최적화를 해보자. $S_{H}(n)$을 빨리 구할 방도를 마련해보자.
\[S_{H}(n)=\sum_{i=1}^{n} \sum_{j=1}^{v} i^{j}=\sum_{j=1}^{v} \sum_{i=1}^{n} i^{j}\]
이렇게 변형하면 dp를 이용해서 우변을 빠르게 계산할 수 있다. 마치 1492번처럼!
이로써 이번 글을 마치겠다. 끝!