# Problem Link

**Author:** Aseem Raj Baranwal

**Tester:** Man Mohan Mishra

**Editorialist:** Aseem Raj Baranwal

# Problem

A k x k matrix M is defined as follows:

- M[i][i] = 1
- M[i][i+1] = 1
- M[i][i-1] = -1
- All other elements are 0

D[k] denotes the determinant of the matrix having dimensions k x k. We need to find, for a given integer **n**, the following sum.

`Summation( GCD(D[i], D[n]) ) for all i from 1 to n`

# Solution

To think of a solution, we need to observe that in the general fibonacci series, if `F[0] = 0`

and `F[1] = 1`

, then `D[k] = F[k+1]`

. So `D[1] = 1`

, `D[2] = 2`

and so on.

Now we look at the term inside the summation: GCD(D[i], D[n]), which is actually GCD(F[i+1], F[n+1]). Applying some basic manipulations using the properties of fibonacci numbers, we can deduce that `GCD(F[a], F[b]) = F[GCD(a, b)]`

(proof)

So now our term inside the summation reduces from GCD(D[i], D[n]) to F[GCD(i+1, n+1)]. We need to sum up all these terms for i = 1 to n. SO effectively, we need to find:

** Summation( F[GCD(i, n+1)] ) for all i from 2 to n+1**.

Letâ€™s take **N = n+1**. We have to find `F[GCD(2, N)] + F[GCD(3, N)] + ... + F[GCD(N, N)]`

. We add and subtract the term F[GCD(1, N)] (which is = 1) to get the expression (S - 1), which will be our final answer, where ** S = Summation( F[GCD(i, N)] ) for all i from 1 to N**.

To compute S in the required time limit, we can preprocess and save S for all n beforehand. To do this, we note than GCD(i, N) can only be a divisor of N. So we compress the summation over the divisors of N as:

** S = Summation( F[d] x Phi(N/d) )** for all d that divide N, because the d

^{th}fibonacci number appears Phi(N/d) times in the summation, as there are Phi(N/d) numbers (say i) <= N such that GCD(i, N) = d.

Now we can use a sieve like approach to store **Phi** and **S** for each N in the range 1 to 10^{5}. Pseudocode below:

```
for(int i = 1; i <= n; i++)
phi[i] = i;
for(int i = 2; i <= n; i++)
if(phi[i] == i)
for(int j = i; j <= n; j += i)
phi[j] -= phi[j]/i;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j += i)
S[j] = (S[j] + (fib[i] * phi[j/i])) % MOD;
```

Now for every query asking the answer for n, we will output (S[n+1] - 1 + MOD) % MOD