피보나치 수의 최대공약수의 합처럼 보이지만...

조만간 2020.05.11(?) problem solving이 올라옵니다. 그 글의 일부였는데, 좀 길어서 분리했습니다.

https://www.acmicpc.net/problem/17405

Step 1

$gcd(F_i, F_j)$ 자체가 너무 커서 주어진 식 그대로는 다항 시간에도 계산을 할 수 없습니다. 하지만, $gcd(F_i, F_j) = F_{gcd(i, j)}$ 임이 잘 알려져 있기 때문에, 이 식을 쓰면 문제는

$\sum_{i = 1}^{n} \sum_{j=1}^{n} gcd(i, j)^k F_{gcd(i, j)}$

가 됩니다. 항의 계산 결과가 gcd에만 의존함에 주목하십시오.

$f(k) = 1 \le i, j \le N, gcd(i, j) = k$ 인 $i, j$ 의 수라고 하면, 위 식은

$\sum_{i = 1}^{n} f(i) i^k F_i$

가 됩니다. 한편, $f(1) = \sum_i 2\phi(i) - 1$ 임을 오일러 파이 함수의 정의에서 쉽게 유도할 수 있습니다. $f(k)$ 는 결국 이 결과에서 양변에 $k$를 곱한 거랑 차이가 없으니,

$g(N) = (\sum_{i=1}^{n} 2\phi(i)) - 1$

라고 하면 답은

$\sum_{i = 1}^{n} g(\lfloor N/i \rfloor) i^k F_i$

가 됩니다. 오일러 파이 함수는 에라토스테네스의 체로 계산할 수 있으니, 여기까지 오면 대충 $O(n \log k)$ 정도의 시간 복잡도가 됩니다.

Step 2

이를 최적화해봅시다. 첫 번째로, $g(X)$ 로 구해야 하는 값이 얼마 되지 않는다는 것을 알 수 있습니다. $\lfloor N / i \rfloor$ 로 가능한 서로 다른 값이 많아야 $\sqrt N$ 개이기 때문입니다. 고로 하나의 $g(X)$ 를 빠르게 구할 수 있으면 됩니다. 이는 오일러 파이 함수의 부분합을 빠르게 구해야 한다는 뜻입니다.

https://codeforces.com/blog/entry/54150 글을 보면 이를 빠르게 하는 방법이 설명되어 있습니다. 간략하게 부연 설명을 하자면, 오일러 파이 함수와, $f(n) = 1$ 의 Dirichlet convolution은 $f(n) = n$ 꼴입니다 (이 사실은 정의에서 어렵지 않게 유도 가능합니다. 이 위키백과 링크에 가시면 이러한 디리클레 곱의 테이블이 적혀 있습니다) 고로 위 글에 나와있는 테크닉을 그대로 적용하면 계산이 가능합니다. 하나의 $g(X)$ 를 구하는데 $O(n^{2/3})$ 이라서 느리다고 생각할 수 있지만, 사실 $g(N)$ 을 구하는 과정에서 $g(\lfloor N / i \rfloor)$ 꼴의 모든 함수가 계산되기 때문에 전혀 느리지 않습니다. 고로 이 사실을 사용하면 $O(n^{2/3})$ 전처리로 $g(X)$로 필요한 모든 값을 계산할 수 있습니다. 이제 $g$ 함수가 대충 $O(\log N)$ 정도에 계산 가능하다고 생각할 수 있습니다. 

다시 원래 식으로 넘어옵시다. $g(X)$ 의 값을 구할 수 있으니, 이제 작은 $n$에 대해서는 $O(n \log k)$ 시간에 문제를 해결할 수 있습니다 (대략 300만까지 했다고 합시다.) 큰 n에 대해서는, 서로 다른 $g(\lfloor N / i \rfloor)$ 의 개수가 300개 이하입니다. 고로 고정된 $k$에 대해서

$\sum_{i = 1}^{n} i^k F_i$

꼴의 부분합을 $n \le 10^9$ 정도 범위에서 한 300번 정도 계산할 수 있으면 됩니다.

Step 3

이를 위해 다음 사실을 사용합니다.

Lemma 1. 다항식 $P(x)$ 에 대해서, $F_P(X, t) = \sum_{i = 0}^{t} P(X + i) \binom{t}{i} (-1)^i$ 라고 하자. $\Delta P(x) = P(x) - P(x + 1)$ 이라고 하면, $t> 0$ 에서 $F_P(X, t) = F_{\Delta P}(X, t - 1)$ 이 성립한다.

Proof.

$F_{\Delta P}(X, t - 1) = \\ \sum_{i = 0}^{t - 1}(P(X + i) - P(X + i + 1)) \binom{t-1}{i} (-1)^i = \\ \sum_{i = 0}^{t} P(X + i) (\binom{t-1}{i} + \binom{t-1}{i-1})(-1)^i=\\ \sum_{i = 0}^{t} P(X + i) \binom{t}{i}(-1)^i$

Remark. 다항식에 대해서 Berlekamp-Massey로 interpolation할 수 있는 이유가 이것입니다. (근데 제가 몇번 해봤는데, 그냥 Lagrange interpolation이 훨씬 낫습니다. 벌레로 하지 마세요.)

Theorem 1. 다항식 $P(x)$ 에 대해서, $F_P(X, t) = \sum_{i = 0}^{t} P(X + i) \binom{t}{i} (-1)^i$ 일 때, $h_P(X, c) = \sum_{i = 0}^{k} f_P(X, i) F_{c + 2i + 1}$ 로 정의하면, $h_P(X+1, c + 1) - h_P(X, c) = F_c P(X)$ 이다.

Proof. 차수에 대한 수학적 귀납법을 사용하자. $P(X) = 0$ 이면 자명하다. $P$ 보다 작은 차수에 대해서 명제가 증명되었다고 하자.

$h_P(X, c) = \\ \sum_{i=0}^{k} f_P(X, i) F_{c + 2i + 1} = \\ \sum_{i = 0}^{k-1} F_{\Delta P}(X, i) F_{c+2i+3} + F_{P}(X, 0) F_{c+1} = \\ h_{\Delta P}(X, c + 2) + P(X)F_{c+1}$

이를 통해 정리하면

$h_P(X+1, c + 1) - h_P(X, c) = \\ h_{\Delta P}(X+1, c+3) - h_{\Delta P}(X, c+2) + P(X+1)F_{c+2} - P(X)F_{c+1} = \\ F_{c + 2}(\Delta P)(X) + P(X+1)F_{c+2} - P(X)F_{c+1}= \\ F_{c + 2}(P(X) - P(X + 1)) + P(X+1)F_{c+2} - P(X)F_{c+1} = \\ F_c P(X)$

가 성립한다.

$P(X) = X^k$ 로 두면, $F_P(X, t) = \sum_{i = 0}^{t} (X + i) ^k \binom{t}{i} (-1)^i$. $h_P(X, c) = \sum_{i = 0}^{k} f_P(X, i) F_{c + 2i + 1}$ 와 같이 풀어쓸 수 있습니다. Theorem 1의 결과로, $h_P(X + 1, X + 1) - h_P(1, 1) = \sum_{i = 1}^{X} F_i i^k$ 가 됩니다. 피보나치 함수를 $O(\log N)$ 시간에 다항식 나눗셈으로 계산해 주면, 고로 각 항을 $O(k^2)$ 시간에 계산할 수 있습니다.

Step 4

비슷한 형태의 다항식을 여러 쿼리에 대해서 계산하는 게 문제이니, 계산하기 쉽게 전처리 해 줍시다. $f_P(X, i)$ 자체는 $X$ 에 대한 $k$ 차 다항식이라 적당히 계산할 수 있으면 쿼리 당 $O(k)$ 에 계산할 수 있습니다. 하지만 우리가 실제로 계산해야 하는 $h_P(X, X)$ 는 $F_{X + 2i + 1}$ 꼴의 수들에 종속적이기 때문에 최적화하기 어렵습니다. 고로 다음과 같은 식을 사용합시다:

$F_{m+n-1} = F_m F_n + F_{m-1} F_{n-1}$

그러면, $F_{X+2i+1} = F_{X+1} F_{2i+1} + F_{X} F_{2i}$ 이 됩니다. 위 식에 대입하면:

$h_P(X, X) = \sum_{i = 0}^{k} f_P(X, i) F_{X + 2i + 1} = \\ \sum_{i = 0}^{k} f_P(X, i) (F_{X+1} F_{2i+1} + F_{X} F_{2i}) =\\ F_{X + 1} \sum_{i = 0}^{k} f_P(X, i) F_{2i+1} + F_{X} \sum_{i = 0}^{k} f_P(X, i) F_{2i}$

고로, $g_1(X) = \sum_{i = 0}^{k} f_P(X, i) F_{2i+1} , g_2(X) = \sum_{i = 0}^{k} f_P(X, i) F_{2i}$ 라고 하면, $h_P(X, X) = g_1(X) F_{X + 1} + g_2(X) F_{X}$ 가 됩니다.

Step 5

$X$ 가 주어질 때, $g_1(X) = \sum_{i = 0}^{k} (\sum_{j = 0}^{i} (X + j) ^k \binom{i}{j} (-1)^j) F_{2i+1}$ 이라는 식을 빠르게 계산해 봅시다. $g_2(X)$ 는 거의 같은 방법으로 할 수 있으니 생략합니다.

$g_1(X) = \sum_{i = 0}^{k} (\sum_{j = 0}^{i} (X + j) ^k \binom{i}{j} (-1)^j) F_{2i+1} = \\ \sum_{j=0}^{k} (\sum_{i = j}^{k} (X + j) ^k \binom{i}{j} (-1)^j) F_{2i+1} = \\sum_{j=0}^{k} (-1)^j (X + j) ^k (\sum_{i = j}^{k} \binom{i}{j} F_{2i+1}) = $

$A_j = \sum_{i = j}^{k} (\binom{i}{j} F_{2i+1})$ 라고 하면

$A_j = \sum_{i = j}^{k} (F_{2i+1} i! \frac{1}{(i-j)! j!}) = \frac{1}{j!} \sum_{i = j}^{k} \frac{F_{2i+1}}{(i-j)!}$

고로 $A_j$ 를 FFT로 구할 수 있습니다. 그러면

$g_1(X) = \sum_{j=0}^{k} (-1)^j (X + j) ^k A_j$

가 되어서 각 항을 $O(k \log k + \log N)$ 에 계산할 수 있습니다.

Challenge

$n \le 5 \times 10^{11}$ 일 때도 풀 수 있을 줄 알았으나 아니었습니다. 할 수 있을까요?