不过cxlove大牛的写法不是hash表实现（读书少，说错了请指正），弱渣用hash表实现了一下。。。。。
hdu 2815 mod tree http://acm.hdu.edu.cn/showproblem.php?pid=2815 几个坑点：输出can‘t上面的确是全角，不是半角，手残手动改成了半角。。。。。还有一个地方就是余数n的值应该小于mod的值。。。。。
/************************************************************** Problem:hdu 2815 User: youmi Language: C++ Result: Accepted Time:62MS Memory:2764K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int n,p,b; const int seed=65535; struct Hh { int id,next; ll val; }hs[seed<<1]; bool flag[seed<<1]; int top; void ins(int id,ll val) { int k=val&seed; if(flag[k]==false) { flag[k]=true; hs[k].next=-1; hs[k].id=id; hs[k].val=val; return ; } while(hs[k].next!=-1) { if(hs[k].val==val) return ; k=hs[k].next; } hs[k].next=++top; hs[top].next=-1; hs[top].id=id; hs[top].val=val; } int get_find(ll val) { int k=val&seed; if(flag[k]==false) return -1; while(k!=-1) { if(hs[k].val==val) return hs[k].id; k=hs[k].next; } return -1; } ll q_mul(ll a,ll b,ll mod) { ll res=0; a=a%mod; while(b) { if(b&1) res=(res+a)%mod; b>>=1; a=(a<<1)%mod; } return res; } ll q_pow(ll a,ll b,ll mod) { ll res=1; a=a%mod; while(b) { if(b&1) res=q_mul(res,a,mod); b>>=1; a=q_mul(a,a,mod); } return res; } ll ex_gcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll ans=ex_gcd(b,a%b,x,y); ll temp=x; x=y; y=temp-y*(a/b); return ans; } ll inval(ll a) { ll x,y; ex_gcd(a,p,x,y); return (x*n%p+p)%p; } ll babystep() { top=seed; ll buf=1%p; ll D=buf,temp,x,y; int d=0; for(int i=0;i<=100;buf=buf*b%p,i++) if(buf==n) return i; while((temp=ex_gcd(b,p,x,y))!=1) { if(n%temp) return -1; ++d; p/=temp,n/=temp; D=D*(b/temp)%p; } int m=(int)ceil(sqrt((double)p)); buf=1%p; for(int i=0;i<=m;buf=buf*b%p,i++) ins(i,buf); ll bm=q_pow(b,m,p); for(int i=0;i<=m;i++,D=D*bm%p) { temp=inval(D); int w; if(temp>=0&&(w=get_find(temp))!=-1) return i*m+w+d; } return -1; } int main() { //freopen("in.txt","r",stdin); while(~sc3(b,p,n)) { if(n>=p) { puts("Orz,I can’t find D!"); continue; } zeros(flag); n%=p; ll pos=babystep(); if(pos==-1) puts("Orz,I can’t find D!"); else printf("%I64d ",pos); } return 0; }