# SPIT05- Editorial

Practice

Contest

Author : Vikesh Tiwari

Editorialist: Vikesh Tiwari

medium-hard

## PREREQUISITES

data structures,maths, number theory

## PROBLEM

Chef has list of all Fibonacci Numbers but in modulo 1013. This list in infinite.

We know that Fibonacci sequence starts with 0 and 1. So in this list each number apart from first two, is sum of previous two numbers modulo 1013.

ex : (a+b)mod 1013.

So beginning of the list looks like : 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Now you’re given an integer n, find first occurrence of n in the given list. (0-indexed)

## EXPLANATION

Main idea: baby-step-giant-step.

In this problem we had some Fibonacci number modulo 1013, and we had to determine the position of its first occurence in Fibonacci sequence modulo 1013.

• Let a and b be two different coprime modula — divisors of 1013.
• Find all occurences of number ![](upload://7j0FSlCtNOf37zXEo69bCJODtIU.png) in Fibonacci sequence modulo a period.
• Find all occurences of number ![](upload://yCIivz5spxFsopfMaqWlvh4eQyz.png) in Fibonacci sequence modulo bperiod.
• Let's fix a pair of such occurences. Let the occurence modulo a be in position i, and the occurence modulo b be in position j.
• Let t(m)be Fibonacci sequence modulom period.
• From the Chinese Remainder Theorem, it follows that t(ab) = LCM(t(a), t(b)) (remember that a and b are coprime).
• Then from fixed occurences of f in periods of sequences modulo a and b we can recover the position of occurence of f in period of sequence modulo ab. It could be done by solving the following Diophantine equation: i + t(a) * x = j + t(b) * y. We can solve it using a simple bruteforce of one of the roots.
• If the occurence in sequence modulo ab period ( we have just found it) is u, then every occurence f in Fibonacci sequence modulo 1013 period can be represented as t(ab) * k + u. Then let's bruteforce k and find all occurences in sequence modulo 1013 period. To determine Fibonacci number on position α + t(ab) from known Fibonacci number on position α, we need to multiply the vector (Fα, Fα + 1) and some matrix.
• Let's choose a = 59 and b = 213. Note that there is no number that occur Fibonacci sequence modulo a or b period more than 8 times. That means that total count of pairs will never be greater than 64. For each occurence we'll bruteforce not more than ![](upload://7kBMc0Dk6gHlbkEnAd0S6aIpTbC.png) numbers. That was the author's solution.

Also that was possible to use the fact that for any number the count of its occurences in period of sequence modulo <span tex-span">10<sup upper-index">p (for any natural <span tex-span">p) is not big more efficiently. From occurences in sequence modulo <span tex-span">10<sup upper-index">i period we could get occurences in sequence modulo <span tex-span">10<sup upper-index">i + 1 period using the method we use to jump from modulus <span tex-span">ab to modulus <span tex-span">10<sup upper-index">13.

# C++ Code

``````//Strange Fibonacci
//Fibonacci Using Matrix
#include<cstdio>
#include<cstring>
typedef long long ll;
ll mod,ans,res;
ll mul(ll a,ll b){
return b==0?0:((mul(a,b>>16)<<16)+a*(b&(1<<16)-1))%mod;
}
void mul(ll f,ll g){
ll a;
a=(mul(f,g)+mul(f,g))%mod;
a=(mul(f,g)+mul(f,g))%mod;
a=(mul(f,g)+mul(f,g))%mod;
a=(mul(f,g)+mul(f,g))%mod;
memcpy(f,a,sizeof a);
}
void init(ll g){
g=g=1,g=g=0;
}
void quick(ll f,ll n){
ll g;
for (init(g);n;n>>=1){
if (n&1) mul(g,f);
mul(f,f);
}
memcpy(f,g,sizeof g);
}
void init1(ll f){
f=0,f=f=f=1;
}
bool dw(ll g){
return g==1 && g==1 && !g && !g;
}
int main(){

ll n,tm;
ll f,g,h;
int i,j,k,cnt,pp;
scanf("%lld",&n);
for (mod=tm=1,cnt=1,ans=0,i=0;i<13;i++){
mod=mod*10;
init1(f);
quick(f,tm);
init(g),pp=0,j=0;
do{
for (k=0;k<cnt;k++){
init1(h);
quick(h,ans[k]+tm*j);
if (h==n%mod) res[pp++]=ans[k]+tm*j;
}
mul(g,f);
j++;
} while (!dw(g));
memcpy(ans,res,sizeof res);
cnt=pp;
tm*=j;
}
printf("%lld\n",cnt==0?-1:ans);
return 0;
}
``````

Nice editorial. Thanks