【BZOJ】3239: Discrete Logging

http://www.lydsy.com/JudgeOnline/problem.php?id=3239

题意：原题很清楚了= =

#include <bits/stdc++.h>
using namespace std;

map<int, int> s;
typedef long long ll;
int mpow(int a, int b, int p) {
	a%=p; int r=1;
	while(b) { if(b&1) r=((ll)r*a)%p; a=((ll)a*a)%p; b>>=1; }
	return r;
}
void work(int a, int b, int p) {
	a%=p; b%=p;
	if(b==1) { puts("0"); return; }
	if(!a && !b) { puts("1"); return; }
	if(!a) { puts("no solution"); return; }
	s.clear();
	int m=sqrt(p+0.5), t=1, w=a, mm;
	for(int i=0; i<m; ++i) s[((ll)b*t)%p]=i, t=((ll)t*w)%p;
	w=mpow(a, m, p); t=1; mm=(p-1)/m+1; bool flag=1;
	for(int i=0; i<=mm; ++i) if(s.count(t) && ((ll)m*i-s[t])>=0) { printf("%lld
", (ll)m*i-s[t]); flag=0; break; } else t=((ll)t*w)%p;
	if(flag) puts("no solution");
}
int main() {
	int a, b, p;
	while(~scanf("%d%d%d", &p, &a, &b)) work(a, b, p);
	return 0;
}

　　

bsgs裸题= =