Author: Aseem Raj Baranwal
Tester: Man Mohan Mishra
Editorialist: Aseem Raj Baranwal
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
To think of a solution, we need to observe that in the general fibonacci series, if
F = 0 and
F = 1, then
D[k] = F[k+1]. So
D = 1,
D = 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