DETDET - Editorial

editorial
, , , ,
1

Problem Link

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