# DETDET - Editorial

Contest

Practice

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 dth 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 105. 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