Today has not been a productive day. I was able to finish compiling some dependencies to build a kernel… but other than that, I didn’t do too much. Anyway, this problem is not difficult. I think, it should be something like $15\%$: Primonacci.
I did a bit of a trick, because I calculated the prime numbers separately and saved them in a text file. Mathematica was really helpful and fast to calculate primes in a range. Something as simple as:
Prime[Range[PrimePi[10^14]+1, PrimePi[10^14]+10^5]]
it’s enough to generate the primes needed for the problem.
Now, the problem requires calculating the Fibonacci values of these prime numbers and adding them up.
You know, Fibonacci numbers have an exponential growth, so it is expected to have large numbers here. Fortunately, the problem only requires to calculate it under mod 1234567891011.
We need a logarithmic method to calculate the fibonacci numbers quickly. I will explain how matrices can help here.
Take a look to the next equation:
\begin{aligned} \begin{pmatrix} 1 & 1\cr 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n-1}\cr F_{n-2} \end{pmatrix} = \begin{pmatrix} F_{n}\cr F_{n-1} \end{pmatrix} \end{aligned}
It’s the matrix definition of a fibonacci number. Now, I’ll extend it more:
\begin{aligned} \begin{pmatrix} 1 & 1\cr 1 & 0 \end{pmatrix} \cdot \bigg(\begin{pmatrix} 1 & 1\cr 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n-2}\cr F_{n-3} \end{pmatrix} \bigg) = \begin{pmatrix} F_{n}\cr F_{n-1} \end{pmatrix} \end{aligned}
It still makes sense, doesn’t it? Now, take a look at this:
\begin{aligned} \begin{pmatrix} 1 & 1\cr 1 & 0 \end{pmatrix} \cdot \bigg(\begin{pmatrix} 1 & 1\cr 1 & 0 \end{pmatrix} \cdots \bigg(\begin{pmatrix} F_{1}\cr F_{0} \end{pmatrix} \bigg) \cdots \bigg) &= \begin{pmatrix} F_{n}\cr F_{n-1} \end{pmatrix}\cr \begin{pmatrix} 1 & 1\cr 1 & 0 \end{pmatrix}^{n-1} \cdot \begin{pmatrix} F_{1}\cr F_{0} \end{pmatrix} &= \end{aligned}
Probably, you know how to do exponentiation efficiently. It is a well-known algorithmic method called divide and conquer, and in this case it is binary exponentiation. I will explain it only for integers, but it applies also for matrices.
Suppose that, you want to calculate: $2^{10}$:
The algorithm does the following:
$2^{10} = 2^{5} * 2^{5}$
$2^{5} = 2^{2} * 2^{2} * 2$
$2^{2} = 2*2$
and it’s all. As you can see, in each step we divide the exponent by two, if the exponent is even, we’ll have two equal powers, if the exponent is odd we can simply subtract 1 of the exponent and proceed as if it was even.
Since in each step we are dividing the exponent by two, the expected number of operations is $\log_{2} n$. So, this algorithm is logarithmic.
Back to the problem. We have a way to calculate big fibonacci numbers under a mod in logarithmic time. So, even if the numbers are huge, we can calculate them quickly.
#include <bits/stdc++.h>
using namespace std;
using ll = __int128;
#define MOD 1234567891011
typedef vector<vector<ll> > Matrix;
Matrix ones(int n) {
Matrix r(n,vector<ll>(n));
for(int i=0; i<n; i++) r[i][i]=1;
return r;
}
Matrix operator*(Matrix &a, Matrix &b){
int n=a.size(),m=b[0].size(),z=a[0].size();
Matrix r(n,vector<ll>(m));
for(int i=0; i<n; i++)for(int j=0; j<m; j++)for(int k=0; k<z; k++)
r[i][j]+=a[i][k]*b[k][j],r[i][j]%=MOD;
return r;
}
Matrix be(Matrix b, ll e) {
Matrix r=ones(b.size());
while(e){if(e&1LL)r=r*b;b=b*b;e>>=1;}
return r;
}
ll fib(ll n){
Matrix fibo(2, vector <ll>(2));
fibo[0] = {1, 1};
fibo[1] = {1, 0};
Matrix F = be(fibo, n);
return F[1][0]%MOD;
}
int main(){
unsigned long long p;
ll ans = 0;
while(cin >> p){
ans += fib(p);
ans %= MOD;
}
unsigned long long out = ans;
cout << out << '\n';
return 0;
}
This code runs on my computer in just 4s.