题目

代码:

#include<cstdio>
#include<map>
#include<tr1/unordered_map>
#include<cmath>
#define int long long

int p,a,b;
std::tr1::unordered_map<int,int> mp;
const int q = 1e9+7;

int qpow(int x,int y) {
	int ans = 1;
	while(y) {
		if(y & 1) ans = ans * x % p;
		x = x * x % p;
		y >>= 1;
	}
	return ans;
}

int gcd(int x,int y) {
	return y?gcd(y,x%y):x;
}

void exgcd(int x, int y, int& xx, int& yy) {
	if (y == 0) {
		xx = 1, yy = 0;
		return;
	}
	exgcd(y, x % y, yy, xx);
	yy -= x / y * xx;
}

int inv(int x,int mod) {
	int xx,y;
	exgcd(x,mod,xx,y);
	return (xx%mod+mod) % mod;
}

int bsgs(int x,int y,int mod) {
	mp.clear();
	int sq = sqrt(mod) + 1;
	int temp = y;
	for(int i = 0; i <= sq; i++)
		mp[temp] = i,
		           temp = 1ll * temp * x % mod;
	x = qpow(x,sq);
	if(!x) return b==0?1:-1;
	for(int i = 1,val = 1; i <= sq; i++) {
		val = 1ll * val * x % mod;
		if(mp.find(val) != mp.end()) return i*sq-mp[val];
	}
	return -1;
}

int exbsgs(int x,int y,int mod) {
//	x %= mod;
//	y %= mod;
	if(y==1 or mod==1)return 0;
	int d=gcd(x,mod),k=0,mul=1;
	while(d!=1) {
		if(y%d)return -1;
		k++;
		y/=d;
		mod/=d;
		mul=1ll*mul*(x/d)%mod;
		if(mul==y)return k;
		d=gcd(x,mod);
	}
	int f=bsgs(x,1ll*y*inv(mul,mod)%mod,mod);
	if(f==-1)return -1;
	return f+k;
}

signed main() {
	scanf("%lld%lld%lld",&p,&a,&b);
	do {
		int op = exbsgs(a,b,p);
		if(op == -1) printf("No Solution\n");
		else printf("%lld\n",op);
		scanf("%lld%lld%lld",&p,&a,&b);
	} while(a != 0 and b != 0 and p != 0);
}

问题:

样例过不去，但是照着题解感觉写的差不多...