[BOJ 16123] 피타고라스 쌍

문제에서 주어진 조건으로부터 $(n,m)=1$이고 $m\not\equiv n\pmod{2}$라는 사실을 알 수 있다. 그럼 우리가 구하고자 하는 값은 다음과 같다.

\[\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][n=odd][m=even]\]

위 식을 변형 시키면 다음을 얻는다.

\[=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1](1-[2|n])[2|m]\]

\[=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][2|m]-\sum_{n=1}^{L}\sum_{m=1}^{L}[(n,m)=1][2|n][2|m]\]

이때 오른쪽 항은 항상 0이 된다는 사실을 알 수 있다.

\[=\sum_{n=1}^{L}\sum_{m=1}^{L}\sum_{s=1}^{L} \mu(s)[s|n][s|m][2|m]\]

\[=\sum_{s=1}^{L}\mu(s)\sum_{n=1}^{\lfloor \frac{L}{s}\rfloor}\sum_{m=1}^{\lfloor \frac{L}{s}\rfloor}[2|sm]\]

이때 $s$가 짝수인 경우와 홀수인 경우를 생각하자. 그럼 이 두 경우를 더한 값이 답이 될 것이다. 아래의 식에서 왼쪽 식은 $s$가 홀수인 경우고, 오른쪽 식은 $s$가 짝수인 경우이다.

\[=\sum_{s=1}^{L}\mu(s) \lfloor \frac{L}{s}\rfloor \lfloor \frac{L}{2s}\rfloor  + \sum_{s=1}^{L} \mu(s)\lfloor \frac{L}{s}\rfloor \lfloor \frac{L}{s}\rfloor \]

이 식을 계산할 때 주의할 점은 $\mu(s)$의 합을 홀수인, 짝수인 $s$에 대해서만 구해야 한다는 것인데 이 부분은 다음 식을 이용해서 해결할 수 있다.

\[G(N)=\sum_{n=1}^{N/2}\mu(2n+1),\ S(N)=\sum_{n=1}^{N}\mu(n)\]

위와 같이 정의하면 아래가 성립한다.

\[G(N)-G(N/2)=\sum_{n=1}^{N/2}\mu(2n+1)+\mu(2)\sum_{n=1}^{N/4}\mu(2n+1)=\sum_{n=1}^{N}\mu(n)=S(N)\]

이 식을 $N/2$에 대해서도 반복한다면 다음을 얻는다.

\[G(N)=\sum_{n=1} S(N/2^{n})\]

$S(N)$의 값은 xudyh's sieve를 이용해서 구할 수 있다. 홀수 항의 값을 계산할 수 있으면 짝수 항은 $S(N)-G(N)$이므로 계산할 수 있게 되었다!