SPIT05- Editorial

data-structure
dynamic-programming
editorial
matrices
medium
number-theory

#1

PROBLEM LINK

[Practice][1]
[Contest][2]

Author : Vikesh Tiwari

Editorialist: Vikesh Tiwari

DIFFICULTY

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.
  • Let F be the actual Fibonacci number such that <img align=“middle” tex-formula" src=“http://espresso.codeforces.com/d9ce8bd6dfc05bcffe4c5adfab52889f39344e5b.png” />. Then <img align=“middle"src=“http://espresso.codeforces.com/58b7a9fcb7965b72f8014a6dd64ad3a2ccdeab98.png” /> and <img align=“middle” tex-formula” src=“http://espresso.codeforces.com/267e7cf7d50f13239a730ed84115ae776abc9cb9.png” />.
  • Find all occurences of number in Fibonacci sequence modulo a period.
  • Find all occurences of number 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 <span tex-span">t(ab) = LCM(t(a), t(b)) (remember that <span tex-span">a and <span tex-span">b are coprime).
  • Then from fixed occurences of <span tex-span">f in periods of sequences modulo <span tex-span">a and <span tex-span">b we can recover the position of occurence of <span tex-span">f in period of sequence modulo <span tex-span">ab. It could be done by solving the following Diophantine equation: <span tex-span">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 <span tex-span">ab period ( we have just found it) is <span tex-span">u, then every occurence <span tex-span">f in Fibonacci sequence modulo <span tex-span">10<sup upper-index">13 period can be represented as <span tex-span">t(ab) * k + u. Then let’s bruteforce <span tex-span">k and find all occurences in sequence modulo <span tex-span">10<sup upper-index">13 period. To determine Fibonacci number on position <span tex-span">α + t(ab) from known Fibonacci number on position <span tex-span">α, we need to multiply the vector (<span tex-span">F<sub lower-index">α, F<sub lower-index">α + 1) and some matrix.
  • Let’s choose <span tex-span">a = 5<sup upper-index">9 and <span tex-span">b = 2<sup upper-index">13. Note that there is no number that occur Fibonacci sequence modulo <span tex-span">a or <span tex-span">b period more than <span tex-span">8 times. That means that total count of pairs will never be greater than <span tex-span">64. For each occurence we’ll bruteforce not more than <img align=“middle” tex-formula" src=“http://espresso.codeforces.com/d6df6b79db0ecaf3bc5b2b44480122999f452471.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[1000],res[1000];
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[2][2],ll g[2][2]){
	ll a[2][2];
	a[0][0]=(mul(f[0][0],g[0][0])+mul(f[0][1],g[1][0]))%mod;
	a[0][1]=(mul(f[0][0],g[0][1])+mul(f[0][1],g[1][1]))%mod;
	a[1][0]=(mul(f[1][0],g[0][0])+mul(f[1][1],g[1][0]))%mod;
	a[1][1]=(mul(f[1][0],g[0][1])+mul(f[1][1],g[1][1]))%mod;
	memcpy(f,a,sizeof a);
}
void init(ll g[2][2]){
	g[0][0]=g[1][1]=1,g[0][1]=g[1][0]=0;
}
void quick(ll f[2][2],ll n){
	ll g[2][2];
	for (init(g);n;n>>=1){
		if (n&1) mul(g,f);
		mul(f,f);
	}
	memcpy(f,g,sizeof g);
}
void init1(ll f[2][2]){
	f[0][0]=0,f[0][1]=f[1][0]=f[1][1]=1;
}
bool dw(ll g[2][2]){
	return g[0][0]==1 && g[1][1]==1 && !g[0][1] && !g[1][0];
}
int main(){

	ll n,tm;
	ll f[2][2],g[2][2],h[2][2];
	int i,j,k,cnt,pp;
	scanf("%lld",&n);
	for (mod=tm=1,cnt=1,ans[0]=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[1][0]==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

",cnt==0?-1:ans[0]);
return 0;
}


#2

Nice editorial. Thanks