bzoj5104 Fib数列（BSGS+二次剩余）

快AFO了才第一次写二次剩余的题……

显然应该将Fn写成通项公式（具体是什么写起来不方便而且大家也都知道），设t=((1+√5)/2),T=√5N，然后可以得到t-(-1)/t=√5N，两边同时乘t，移项，得到t-√5Nt-(-1)=0。分别讨论n是奇数或偶数的情况，通过求根公式求t，写个二次剩余即可。

#include<bits/stdc++.h>

using namespace std;

const int sq5=,inv2=5e8+,mod=1e9+,inf=0x7fffffff;

int n,w,ans=inf;

map<int,int>mp;

struct com{

    int x,y;

    com operator*(const com&a)

    {return(com){(1ll*x*a.x+1ll*y*a.y%mod*w)%mod,(1ll*x*a.y+1ll*y*a.x)%mod};}

};

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=;

    }

    return ret;

}

int Sqrt(int n)

{

    if(qpow(n,mod/)!=)return ;

    int a=;

    while(qpow((1ll*a*a%mod-mod-n)%mod,mod/)==)a=rand();

    com x=(com){a,mod-},ans=(com){,};

    int y=inv2;

    w=(1ll*a*a%mod+mod-n)%mod;

    while(y)

    {

        if(y&)ans=ans*x;

        x=x*x,y>>=;

    }

    return ans.x;

}

int BSGS(int t,int n)

{

    int m=ceil(sqrt(mod)),inv=qpow(t,mod-),v=n;

    mp.clear(),mp[n]=mod;

    for(int i=;i<m;i++)v=1ll*v*inv%mod,mp[v]=mp[v]?mp[v]:i;

    if(mp[])return mp[]%mod;

    v=,t=qpow(t,m);

    for(int i=;i<=m;i++)

    {

        v=1ll*v*t%mod;

        if(mp[v])return(i*m+mp[v])%mod;

    }

    return -;

}

int main()

{

    scanf("%d",&n);

    int t=1ll*(sq5+)*inv2%mod,T=1ll*sq5*n%mod,ans=inf;

    int r0=Sqrt(5ll*n*n%mod+),r1=Sqrt(5ll*n*n%mod-),x;

    if(r0)

    {

        x=BSGS(t,1ll*(T+r0)*inv2%mod);

        if(x>-&&x%==)ans=min(ans,x);

        x=BSGS(t,1ll*(T+mod-r0)*inv2%mod);

        if(x>-&&x%==)ans=min(ans,x);

    }

    if(r1)

    {

        x=BSGS(t,1ll*(T+r1)*inv2%mod);

        if(x>-&&x%)ans=min(ans,x);

        x=BSGS(t,1ll*(T+mod-r1)*inv2%mod);

        if(x>-&&x%)ans=min(ans,x);

    }

    if(ans==inf)puts("-1");else printf("%d",ans);

}