Description
Fib数列为1,1,2,3,5,8...
求在Mod10^9+9的意义下，数字N在Fib数列中出现在哪个位置
无解输出-1
Input
一行，一个数字N，N < = 10^9+9
$r_1=\frac{1+\sqrt 5}{2}\\ r_2=\frac{1-\sqrt 5}{2}=-\frac{1}{r_1}\\ N=Fib_x=r_1^x-r_2^x\\ N^2=r_1^{2x}+r_2^{2x}-2(-1)^x\\ ±(r_1^x+r_2^x)=\sqrt{N^2+4(-1)^x}\\ \frac{N±\sqrt{N^2+4(-1)^x}}{2}=r_1^x,-r_2^x\\ x=min(log_{r_1}(\frac{N±\sqrt{N^2+4(-1)^x}}{2}),log_{r_2}(-\frac{N±\sqrt{N^2+4(-1)^x}}{2}))\\ 枚举x的奇偶，利用离散对数计算答案$
#include<cstdio>
typedef long long i64;
const int P=1e9+,g=,sqrt5=,I2=(P+)/,B=;
const int r1=(P++sqrt5)/,r2=(P+-sqrt5)/;
const int lr1=,lr2=;
inline int mul(int a,int b){return (i64)a*b%P;}
inline void muls(int&a,int b){a=mul(a,b);}
inline int fix(int x){return x+(x>>&P);}
int pw(int a,int n){
int v=;
for(;n;n>>=,muls(a,a))if(n&)muls(v,a);
return v;
}
void exgcd(int a,int b,int&x,int&y){
if(!b){x=,y=;return;}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int inv(int a,int b){
int x,y;
exgcd(a,b,x,y);
return (x%b+b)%b;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int solve(int a,int b,int c,int tp){
if(!a)return b?-:-tp;
int g=gcd(a,c);
if(b%g)return -;
a/=g,b/=g,c/=g;
i64 t=(i64)b*inv(a,c)%c;
if(!t)t=c;
if(t%!=tp)t+=c;
return t%!=tp?-:t;
}
int h[][];
int&at(int x){
int w=x&;
while(h[w][]){
if(h[w][]==x)return h[w][];
w=(w+)&;
}
h[w][]=x;
return h[w][];
}
void pre(){
int v=;
for(int i=;i<B;++i){
at(v)=i+;
muls(v,g);
}
}
int log(int x){
int t=pw(g,P--B);
for(int i=;;i+=B){
int y=at(x);
if(y)return y-+i;
muls(x,t);
}
}
int sqrt(int x){
int t=log(x);
return t&?-:pw(g,t/);
}
int ans=-;
void upd(int v){
if(~v&&(v<ans||ans==-))ans=v;
}
void cal(int x,int tp){
upd(solve(lr1,log(x),P-,tp));
upd(solve(lr2,log(fix(-x)),P-,tp));
}
int main(){
pre();
int v;
scanf("%d",&v);
if(!v)return puts("-1"),;
muls(v,sqrt5);
int v2=mul(v,v);
int s1=sqrt(fix(v2-)),s2=sqrt(fix(v2+-P));
if(~s1){
cal(mul(fix(v+s1-P),I2),);
cal(mul(fix(v-s1),I2),);
}
if(~s2){
cal(mul(fix(v+s2-P),I2),);
cal(mul(fix(v-s2),I2),);
}
return printf("%d\n",ans),;
}