[BOJ 17372] 피보나치 수의 최대공약수의 합

문제는 참 간단하다.

\[\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(F_{i},F_{j})\]

를 구하면 된다. 그런데 어떻게 빨리 구하냐가 문제인데... 이 식을 변형해보자. $\gcd(i,j)=d$라고 고정하고 각 $d$에 대해 뭘 계산해야 하는지 알아보자. 변형된 식은 다음과 같다.

\[\sum_{d=1}^{n} F_{d} C(d)\]

여기서 $C(d)$는 $\gcd(i,j)=d$인 쌍의 개수를 의미한다. $F_{d}$인 이유는 $\gcd(F_{i},F_{j})=F_{\gcd(i,j)}$이기 때문! 또한 다음을 알 수 있다.

\[C(d)=2\sum_{i=1}^{n/d} \phi(i) - 1\]

이는 $d=1$일 경우를 생각해보면 편하다. $d=1$일 때 $i$를 고정하고 $j$의 개수를 세자. 이때 $(1,1)=1$인 경우가 2번 세지니까 1을 뺀 것이다. 이렇게 유도된 $C(1)$을 바탕으로 $C(d)$를 유도해낼 수 있다. 이때 $C(d)$가 $N/d$항을 포함하니까 시간복잡도는 $O(\sqrt{N})$이 될 것이다. 우리가 해결해야할 문제는 어떻게 오일러 파이 함수의 합을 빨리 계산하냐는 것이다. 그것은 xudyh's sieve를 사용하면 된다. 이것은 여기 에 자세히 설명되어있다. 나머지는 피보나치 수의 성질을 이용한다면 쉽게 계산할 수 있다.