BSGS算法
给定y、z、p，计算满足yx mod p=z的最小非负整数x。p为质数(没法写数学公式，以下内容用心去感受吧）
设 x = i*m + j.
则 y^(j)≡z∗y^(-i*m)) （mod p）
则 y^(j)≡z∗ine(y^(i*m)) （mod p）(逆元）
由费马小定理y^(p-1)≡1 (mod p) 得 ine(y^m) = y^(p-m-1)
ine(y^(i*m)≡ine(y^((i−1)m))∗y^(p-m-1)
1.首先枚举同余符号左面,用一个hash保存(y^j,j),因为j可能等于0，所以hash[1]要赋为一个特殊值。
2.再枚举同余符号右面，如果hash(z∗ine(y^(i*m)))存在，就找到了一组解。
显然，m=sqrt(p)的时候复杂度最低为O(sqrt(p))，m=ceil(sqrt(p)).
从这个人博客中可以看出，这个人对于BSGS算法有着相当深刻的理解，居然能够找到俩个有助于学习BSGS算法的俩首歌，还用了exgcd算法。
http://www.cnblogs.com/yuiffy/p/3877381.html
其他俩个操作为快速幂，exgcd。
因为题目并不是一起写的，所以写了俩个快速幂。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std; int T,k;
long long y,z,p;
map<int,int> hash; long long q(long long z) {
if(z==) return y%p;
long long m=q(z/);
if(z%) return (((m*m)%p)*y)%p;
return (m*m)%p;
} void solve1() {
printf("%lld\n",q(z));
} long long exgcd(long long a,long long b,long long &x,long long &y) {
if(b==) {
x=; y=;
return a;
}
long long res=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return res;
} void solve2(long long a,long long b,long long n) {
long long x,y,ans,d,s;
d=exgcd(a,n,x,y);
if(b%d!=) printf("Orz, I cannot find x!\n");
else {
ans=(b/d)*x; s=n/d;
ans=(ans%s+s)%s;
printf("%lld\n",ans);
}
} long long power(long long a,long long b,long long mod) {
long long res=;
while(b) {
if(b&) res=res*a%mod;
a=a*a%mod;
b>>=;
}
return res;
} void solve3() {
y%=p; z%=p;
if(!y && !z) printf("1\n");
else if(!y) printf("Orz, I cannot find x!\n");
else {
long long m,v,e,res;
m=ceil(sqrt(p)); v=power(y,p-m-,p); e=; hash.clear();
hash[]=m+;
for(long long i=;i<=m;i++) {
e=e*y%p;
if(!hash[e]) hash[e]=i;
} res=-;
for(long long i=;i<m;i++) {
if(hash[z]) {
res=i*m+(hash[z]==m+?:hash[z]);
break;
}
z=z*v%p;
}
if(res==-) printf("Orz, I cannot find x!\n");
else printf("%d\n",res);
}
} int main() {
scanf("%d%d",&T,&k);
while(T--) {
scanf("%lld%lld%lld",&y,&z,&p);
if(k==) solve1();
else if(k==) solve2(y,z,p);
else solve3();
}
return ;
}