Mod Tree(hdu2815高次线性同余方程)
题意：求每个节点有K个儿子，计算最小深度D的节点数对P取模的结果是N，K^D = N( mod P )的最小D值 如果无解输出 Orz,I can’t find D!
思路：baby__giant算法
分两种情况
第一种 : 当A 和C互质的时候
m = sqrt(C);
A^x = A^i*m+j = B (mod C)
A^i*m*A^j = B ( mod C)
两边除以A^i*m,因为A 和C互质 所以除以A^i*m等于乘以A^i*m的逆元
什么是逆元，当A和C互质 A*b = 1 (mod C) b就是A的乘法逆元 ，所以当存在逆元 B/A = 2 (mod C) 就可以写成B*b = 2(mod C)
所以用扩展欧几里德 求出A^i*m的逆元等于A^-i*m, 化简等于
A^j = A^-i*m * B ( mod C) (0 <= j <= m)
我们可以先算出所有A^j的值存在hash中然后遍历i,计算A^i*m的逆元再乘以B mod C看它的值是否在hash中出现过，如果出现过返回i*m+j
第二种 :当A和C不互质的时候,因为不互质就没有逆元,所以我们要想办法让他们互质 计算A和C的最大公约数
因为 A^x = B (mod C) 如果d = gcd(A,C) 那么 A/d*A^x-1 = B/d ( mod C/d ) 这样一直除下去一直到A和C互质即 (A/d)^c * A^x-c = B/d^c ( mod C / d^c )
这样 A^x-c与C/d^c互质就可以求逆元了,
令k = x-c 紧接着套用上面的计算方式 将k写成 k = i*m+j
然后 (A/d)^c * A^i*m * A^j= B/d^c ( mod C / d^c ) 两边同时除以(A/d)^c * A^i*m,也就是用扩展欧几里德求他们的逆元等于
A^j= B/d^c* ((A/d)^c * A^i*m)^-1 *( mod C / d^c ) 这样还是先算出所有A^j存在hash中然后遍历i,计算((A/d)^c * A^i*m)^-1的逆元再乘以 B/d^c看他的值是否在hash出现过如果出现过返回 i*m+j 因为k = x - c 所以最后的k 还要+ c等于x = i*m+j+c
如果在i的范围(0<= i <= m)都没找到合适的值或者再在化简为互质那一步B/d不能整除那就是无解
因为当解比较小的时候我们可以暴力，那么我们先计算0~~100的如果有就直接返回没有在用上述的算法
本题注意N在 (0 < = N < P) 大于P的都是无解的,还有就是当N = 0的时候就是D = 0,还有大坑就是那个无解的英文千万不能copy
A^x = B (mod p) 0 <= B < p 注意范围，看题目要求如果没有给就按照超范围无解
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<cmath>using namespace std;typedef long long int64;struct Point{ int64 x; int64 y; Point (int64 x,int64 y) : x(x),y(y){}};vector<Point> v[10005];int MOD = 10000;void insert(int64 x,int64 j){ int64 k = x % MOD; Point a(x,j); v[k].push_back(a);}int64 Find(int64 x){ int64 k = x % MOD; int64 temp = v[k].size(); for(int64 i = 0; i < temp; i++) { // printf("%I64d\n",x); if(v[k][i].x == x) return v[k][i].y; } return -1;}int64 gcd(int64 a,int64 b){ if(b == 0) return a; else return gcd(b,a%b);}int64 Exgcd(int64 a,int64 b,int64&x,int64 &y){ if(b == 0) { x = 1,y = 0; return a; } else { int64 r = Exgcd(b,a%b,x,y); int64 temp = x; x = y,y = temp - a/b*y; return r; }}int64 Inval(int64 a,int64 b,int64 n){ int64 x,y,d; d = Exgcd(a,b,x,y);//printf("%I64d %I64d\n",x,y); x = x *n % b; x = ( x % b + b) % b; return x;}int64 baby_gaint(int64 B,int64 N,int64 P){ int64 sum = 1%P; for(int64 i = 0; i <= 100; i++) { if(sum % P == N) return i; sum = ( sum * B ) % P; } int64 cnt = 0,D = 1%P,j,tmp; while((tmp = gcd(B,P)) != 1) { if(N % tmp) { return -1; } cnt++; N = N / tmp; P = P / tmp; D = D * B / tmp % P; } int64 n = (sqrt(1.0*P)); sum = 1; for(int64 i = 0; i < n; i++,sum = (sum * B) % P) { insert(sum,i); } int64 X; for(int64 i = 0;; D = D * sum % P,i+= n) { X = Inval(D,P,N);//printf("%I64d %I64d %I64d\n",X,P,N); if(X >= 0 && ( j = Find(X) ) != -1) { return i + j + cnt; } if(i > P) break; } return -1;}int main(){ int64 K,N,P; while(scanf("%I64d%I64d%I64d",&K,&P,&N) != EOF) { for(int i = 0; i < 10005; i++) v[i].clear(); int64 temp = baby_gaint(K,N,P); if(N >= P) { printf("Orz,I can’t find D!\n");continue; } if(N == 0) { printf("0\n");continue; } if(temp == -1) printf("Orz,I can’t find D!\n"); else printf("%I64d\n",temp); } return 0;}