题目链接：
?pid=2815
题目大意：
有一颗树，每个节点有K个儿子，那么问题来了：能否算出这棵树的最小深度D，使得这个深度
的节点数对P取模的结果为N吗？
思路：
转换一下题目含义，就变成了解K^i = N(mod P)，典型的A^i = B(mod C)问题，此题B的范围
明显在[0，C-1]之间，若不在此区间，，方程显然无解。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#define LL __int64using namespace std;const int MAXN = 65535;struct HASH{int a;int b;int next;}Hash[MAXN*2];int flag[MAXN+66];int top,idx;void ins(int a,int b){int k = b & MAXN;if(flag[k] != idx){flag[k] = idx;Hash[k].next = -1;Hash[k].a = a;Hash[k].b = b;return;}while(Hash[k].next != -1){if(Hash[k].b == b)return;k = Hash[k].next;}Hash[k].next = ++top;Hash[top].next = -1;Hash[top].a = a;Hash[top].b = b;}int Find(int b){int k = b & MAXN;if(flag[k] != idx)return -1;while(k != -1){if(Hash[k].b == b)return Hash[k].a;k = Hash[k].next;}return -1;}int GCD(int a,int b){if(b == 0)return a;return GCD(b,a%b);}int ExGCD(int a,int b,int &x,int &y){int temp,ret;if(!b){x = 1;y = 0;return a;}ret = ExGCD(b,a%b,x,y);temp = x;x = y;y = temp – a/b*y;return ret;}int Inval(int a,int b,int n){int x,y,e;ExGCD(a,n,x,y);e = (LL)x*b%n;return e < 0 ? e + n : e;}int PowMod(LL a,int b,int c){LL ret = 1%c;a %= c;while(b){if(b&1)ret = ret*a%c;a = a*a%c;b >>= 1;}return ret;}int BabyStep(int A,int B,int C){top = MAXN;++idx;LL buf = 1%C,D = buf,K;int d = 0,temp,i;for(i = 0; i <= 100; buf = buf*A%C,++i){if(buf == B)return i;}while((temp = GCD(A,C)) != 1){if(B % temp)return -1;++d;C /= temp;B /= temp;D = D*A/temp%C;}int M = (int)ceil(sqrt((double)C));for(buf = 1%C,i = 0; i <= M; buf = buf*A%C,++i)ins(i,buf);for(i = 0,K = PowMod((LL)A,M,C); i <= M; D = D*K%C,++i){temp = Inval((int)D,B,C);int w;if(temp >= 0 && (w = Find(temp)) != -1)return i * M + w + d;}return -1;}int main(){int A,B,C;while(~scanf("%d%d%d",&A,&C,&B)){if(B > C){printf("Orz,I can’t find D!\n");continue;}B %= C;int temp = BabyStep(A,B,C);if(temp < 0)printf("Orz,I can’t find D!\n");elseprintf("%d\n",temp);}return 0;}
学会技能是小智慧，学会做人是大智慧。
