快AFO了才第一次写二次剩余的题……
显然应该将Fn写成通项公式(具体是什么写起来不方便而且大家也都知道),设t=((1+√5)/2)n,T=√5N,然后可以得到t-(-1)t/t=√5N,两边同时乘t,移项,得到t2-√5Nt-(-1)n=0。分别讨论n是奇数或偶数的情况,通过求根公式求t,写个二次剩余即可。
#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); }View Code