Description
废话不多说，反正小z要说胡话啦！！
小z滔滔不绝地念叨着一串串数字，经过围观群众仔细辨认，猜测他说的正是模10^13意义下的斐波那契数列，我们称之为数列F。
在小z安静下来后，大家都牢牢记住了他所念的最后一个数字，遗憾的是，谁也没有数清小z到底说到了数列的多少项，于是决定求助于你。
给定一个模10^13意义下的非负整数a，求a第一次在数列F中出现是第几项。
这里模意义下的斐波那契数列F定义如下：
Input
一行一个非负整数a,0<=a<10^13
Output
一行一个整数ans，表示a第一次在数列F中出现的位置
如果a不出现在数列F中，输出-1
Sample Input
1
Sample Output
1
HINT
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
矩阵乘法+递归+思路~
因为斐波那契数列在任意一个模数下一定有循环节且是纯循环，所以我们可以想到用map和pair暴力找循环节的方法。但是我用了这种方法成功把我的电脑跑挂了。
由此可见如果直接找数列在1e13下的循环节是不可行的。所以我们可以想到找小一些的模数的循环节，再累积起来计算。
所以我们递归求解，斐波那契数列部分用经典的矩阵快速幂解决，矩阵长这样：
0 1
1 1
其中第一行是第i-1项和第i项。
然后，我们从10开始，把模数逐渐*10，累加上上一个模数的循环节长度，这样，最终最大的模数也不会很大，暴力寻找循环节，再更新答案即可~
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define ll long longconst ll mod=10000000000000;struct node{ll a[2][2];inline node() {memset(a,0,sizeof(a));}
};ll cheng(ll u,ll v)
{ll now=0;for(;v;v>>=1,u=(u+u)%mod) if(v&1) now=(now+u)%mod;return now;
}node operator * (node u,node v)
{node z;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++) z.a[i][j]=(z.a[i][j]+cheng(u.a[i][k],v.a[k][j]))%mod;return z;
}node mi(node u,ll v)
{node z;z.a[0][0]=z.a[1][1]=1;for(;v;v>>=1,u=u*u) if(v&1) z=z*u;return z;
}ll sol(pair<ll,ll> p,node kk,ll u,ll mo)
{if(mo>mod) return 0;map<pair<ll,ll>,ll> ma;node tmp;tmp.a[0][0]=p.first;tmp.a[0][1]=p.second;vector<pair<ll,pair<ll,ll> > > vec;ll now=-1;for(ll i=0;;i++,tmp=tmp*kk){pair<ll,ll> tmp_pa=make_pair(tmp.a[0][0]%mo,tmp.a[0][1]%mo);if(tmp_pa.first==u%mo) vec.push_back(make_pair(i,make_pair(tmp.a[0][0],tmp.a[0][1])));if(!ma.count(tmp_pa)){ma[tmp_pa]=i;continue;}now=i;break;}tmp=mi(kk,now);ll ans=-1;int tot=vec.size()-1;for(ll i=0;i<=tot;i++){ll now1=sol(vec[i].second,tmp,u,mo*10ll);if(now1==-1) continue;now1=vec[i].first+now1*now;if(ans==-1 || ans>now1) ans=now1;}return ans;
}int main()
{ll n;scanf("%lld",&n);node tmp;tmp.a[0][1]=tmp.a[1][0]=tmp.a[1][1]=1ll;printf("%lld\n",sol(make_pair(0ll,1ll),tmp,n,10));return 0;
}