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

向右看齐 2021-11-01 08:44 203阅读 0赞

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int sq5=383008016,inv2=5e8+5,mod=1e9+9,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=1;
        while(b)
        {
            if(b&1)ret=1ll*ret*a%mod;
            a=1ll*a*a%mod,b>>=1;
        }
        return ret;
    }
    int Sqrt(int n)
    {
        if(qpow(n,mod/2)!=1)return 0;
        int a=0;
        while(qpow((1ll*a*a%mod-mod-n)%mod,mod/2)==1)a=rand();
        com x=(com){a,mod-1},ans=(com){
         1,0};
        int y=inv2;
        w=(1ll*a*a%mod+mod-n)%mod;
        while(y)
        {
            if(y&1)ans=ans*x;
            x=x*x,y>>=1;
        }
        return ans.x;
    }
    int BSGS(int t,int n)
    {
        int m=ceil(sqrt(mod)),inv=qpow(t,mod-2),v=n;
        mp.clear(),mp[n]=mod;
        for(int i=1;i<m;i++)v=1ll*v*inv%mod,mp[v]=mp[v]?mp[v]:i;
        if(mp[1])return mp[1]%mod;
        v=1,t=qpow(t,m);
        for(int i=1;i<=m;i++)
        {
            v=1ll*v*t%mod;
            if(mp[v])return(i*m+mp[v])%mod;
        }
        return -1;
    }
    int main()
    {
        scanf("%d",&n);
        int t=1ll*(sq5+1)*inv2%mod,T=1ll*sq5*n%mod,ans=inf;
        int r0=Sqrt(5ll*n*n%mod+4),r1=Sqrt(5ll*n*n%mod-4),x;
        if(r0)
        {
            x=BSGS(t,1ll*(T+r0)*inv2%mod);
            if(x>-1&&x%2==0)ans=min(ans,x);
            x=BSGS(t,1ll*(T+mod-r0)*inv2%mod);
            if(x>-1&&x%2==0)ans=min(ans,x);
        }
        if(r1)
        {
            x=BSGS(t,1ll*(T+r1)*inv2%mod);
            if(x>-1&&x%2)ans=min(ans,x);
            x=BSGS(t,1ll*(T+mod-r1)*inv2%mod);
            if(x>-1&&x%2)ans=min(ans,x);
        }
        if(ans==inf)puts("-1");else printf("%d",ans);
    }

转载于:https://www.cnblogs.com/hfctf0210/p/10887195.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/ce15a31e81df4599823e2adde63d505f.png