大佬的手写Hash。飞快
ll p,b,n; class HASH { public: ll a[100005],inv[100005],mod; HASH() { memset(a,-1,sizeof(a)); mod=100003; } ll Find(ll x) { ll idx=x%mod; while(a[idx]!=x&&a[idx]!=-1)idx=(idx+1)%mod; return a[idx]==x?inv[idx]:-1; } void Insert(ll x,ll val) { ll idx=x%mod; while(a[idx]!=-1)idx=(idx+1)%mod; a[idx]=x; inv[idx]=val; } }; ll powmod(ll a,ll n,ll p) { ll r=1; while(n) { if(n&1)r=(r*a)%p; a=(a*a)%p; n>>=1; } return r; } ll bsgs(ll b,ll n,ll p) { HASH sh; ll m=ceil(sqrt(p*1.0)),temp=1; for(int i=0;i<=m;++i) { sh.Insert(temp,i); temp=temp*b%p; if(temp==1)break; } ll inv=powmod(powmod(b,m,p),p-2,p); temp=n; for(int i=0;i<=p/m;++i) { ll r=sh.Find(temp); if(r!=-1)return i*m+r; temp=temp*inv%p; } return -1; } map实现hash，常数大的飞起 typedef long long ll; ll powermod(ll bit,ll n,ll mod) { ll ans=1; bit = bit % mod; while(n) { if(n & 1) ans = ans * bit %mod; bit = bit * bit % mod; n>>=1; } return ans; } ll bsgs(ll a,ll b ,ll p) { ll m ,inv,temp=1; m= ceil(sqrt(p+0.5)); inv = powermod(a,p-m-1,p); map<ll ,ll> myp; myp[1]=m; for(int i=1;i<m;++i) { temp = (temp * a) %p; if(!myp[temp]) myp[temp] = i; } for(int i=0;i<m;++i) { if(myp[b]) { ll num=myp[b]; myp.clear(); return i*m + (num == m? 0:num); } b = (b*inv)%p; } return -1; }
