PS 일지 (2022.06.30)

17372. 피보나치 수의 최대공약수의 합

Diamond 2

문제 분석

피보나치 수는 다음과 같은 규칙으로 만들어지는 수열이다.

처음 몇 개의 항은 다음과 같다.

이때 다음 합을 구하는 문제이다.

이때 $\gcd$는 두 수의 최대공약수를 의미한다.

$n$ 이 $10^9$ 까지 커질 수 있으므로 무조건 $O(n)$ 미만으로 깎아야 한다.

풀이

피보나치 수의 성질

우선 피보나치수의 성질을 이용해서 다음과 같이 정리하자.

해당 성질의 증명은 GCD of Fibonacci Numbers에 있다.

아직도 시간 내에 풀기에는 불가능하므로 $\sum$을 하나 떼어내 보자.

이를 위해 $\gcd(i, j) = d$를 만족하는 $(i, j)$의 개수를 세서 같은 $d$를 가진 피보나치 수끼리 묶어보자.

위 개수를 $cnt_n(d)$ 라고 하면 아래와 같이 식이 정리된다.

cnt(d)에 대한 고찰

물론 일일히 모든 $(i, j)$ 쌍을 검사할 수도 있지만, 그러면 시그마를 떼어낸 의미가 없다.

따라서 다음과 같이 $cnt$를 수정하자.

그리고 $cnt_n(1) = S(n)$ 이라고 표현하자. 그러면 식은 여기까지 정리된다.

$S(n)$ 은 어떻게 구할 수 있을까?

우선 $S(n)$ 은 $n \times n$ 격자에서 좌표가 서로소인 점들의 개수이다.

따라서 격자의 개수 $n^2$에서 $\gcd(i, j) = 2, ... n$ 을 하나씩 빼주면 된다.

완성된 식은 다음과 같다.

S(N) 개선

하지만 이것도 너무 느리다. 좀 더 개선해보자.

$\lfloor n/d \rfloor$를 잘 보면 $d$가 $n$에 가까워질 수록 변화가 거의 없다는 것을 알 수 있다.

여기에서 착안해서 함수를 두 부분으로 나눌 수 있다.

이러한 트릭은 xudyh's sieve 또는 Mertens Trick 이라고 불리고, 전처리 과정을 포함한다면 $O(n^{2/3})$ 으로 계산할 수 있다고 알려져있다.

다시 돌아와서

$S(n)$을 개선할 때 사용한 아이디어를 다시 활용해보면 다음과 같이 정리할 수 있다.

풀고 있는 문제 리스트(Diamond II)

• 정수론 (1/23)