poj 2417 离散对数模方程+哈希

2019-04-14 21:30发布

站内文章 / 模拟电子
14006 0 1309
事实又证明map慢死啦，慢了不知道多少倍 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define mod 10007 ll pow_mod(ll a,ll n,ll m) // a^n(mod m) { ll res=1; a%=m; while(n) { if(n&1) { res*=a; if(res>=m) res%=m; } a*=a; if(a>=m) a%=m; n>>=1; } return res; } struct Hash { int val; ll sign; Hash *nxt; Hash(int _val=0,ll _sign=0) { val=_val; sign=_sign; nxt=NULL; } }*h[mod+10]; int getkey(ll n) { return n%mod; } void hash_insert(ll n,int val) { int k=getkey(n); if(h[k]==NULL) { h[k]=new Hash(val,n); } else { Hash *p=h[k]; while(p->nxt!=NULL) p=p->nxt; p->nxt=new Hash(val,n); } } int hash_find(ll n) { int k=getkey(n); if(h[k]==NULL) return -1; Hash *p=h[k]; while(p!=NULL) { if(p->sign==n) return p->val; p=p->nxt; } return -1; } ll log_mod(ll B,ll N,ll P) { memset(h,NULL,sizeof(h)); int m=sqrt(P+0.5)+1; ll t=1,t2; ll inv=pow_mod(B,P-2,P); ll B_m=pow_mod(inv,m,P); for(int i=0;i=0) return (ll)(i*m+temp); t=t*B_m%P; } return -1; } int main () { ll P,B,N; while(scanf("%lld%lld%lld",&P,&B,&N)!=EOF) { ll ans=log_mod(B,N,P); if(ans<0) printf("no solution "); else printf("%lld ",ans); } return 0; }

热门文章