题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3239
离线版题目：http://paste.ubuntu.com/19379662/
BSGS 的板题，然而把MAXINT记成2e10去了，调试了两个小时QAQ
BSGS 见算法总结，这么晚了，今天先扔一份代码就跑了吧QAQ
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 9999971;
int p,a,b;
namespace Hash{
const int N = 10000000;
const int MOD = 9999971;
const int INF = 2000000000;
int T,nxt[N/2],v1[N/2],head[N],v2[N/2];
inline void insert(int w, int num){
v1[++T] = w; v2[T] = num;
nxt[T] = head[w%MOD]; head[w%MOD] = T;
}
inline void init(){
memset(head,0,sizeof(head));
T = 0;
}
inline int query(int w){
int ret = INF;
for (int i=head[w%MOD];i;i=nxt[i])
if (v1[i] == w) ret = min(ret, v2[i]);
if (ret != INF) return ret;
else return -1;
}
};
inline int quick_pow(int w, int t){
int ret = 1;
while (t) {
if (t & 1) ret = ((LL)ret*w) % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}
inline void BSGS(){
Hash::init();
if (b == 1) printf("0\n");
else {
int w = a, lim = ceil(sqrt(p));
for (int i=1;i<=lim;i++) {
if (w == b) {printf("%d\n",i); return;}
Hash::insert(w,i); w = (LL)w*a%p;
}
a = w = quick_pow(a,lim);
for (int i=1;i<=lim;i++) {
int tmp = Hash::query((LL)b*quick_pow(w,p-2)%p);
if (tmp > -1) {printf("%d\n",lim*i+tmp); return;}
w = (LL)w*a%p;
}
printf("no solution\n");
}
}
int main(){
while (~scanf("%d%d%d",&p,&a,&b)) BSGS();
return 0;
}
Hi are using WordPress for your site platform? I’m new to the blog world
but I’m trying to get started and set up my own. Do
you require any html coding expertise to make your own blog?
Any help would be really appreciated!
Hi, i think that i saw you visited my weblog so i came to
“return the favor”.I’m attempting to find things to enhance my site!I suppose its ok to use a
few of your ideas!!
Your style is so unique compared to other folks I’ve read stuff
from. Thanks for posting when you’ve got the opportunity, Guess I will just
bookmark this site.
Hi there! Someone in my Facebook group shared this website
with us so I came to give it a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
Exceptional blog and excellent design.
Hi there to all, how is the whole thing, I think every one is getting more from this site, and
your views are nice for new visitors.
Ahaa, its pleasant dialogue on the topic of this piece of writing at this place
at this web site, I have read all that, so now me also commenting at this place.
Thanks for the marvelous posting! I really enjoyed reading
it, you may be a great author.I will ensure
that I bookmark your blog and will come back sometime soon. I want to encourage you
to ultimately continue your great posts, have a nice
evening!
Greetings! Very helpful advice within this article! It’s the little changes which
will make the greatest changes. Many thanks for sharing!
Wonderful beat ! I wish to apprentice while you amend your site, how can i subscribe for a blog website?
The account aided me a acceptable deal. I had been tiny
bit acquainted of this your broadcast offered bright clear idea
My partner and I stumbled over here by a different web page and thought I might as well check things out.
I like what I see so i am just following you. Look forward to looking at
your web page for a second time.
you’ve gotten an awesome weblog right here! would you prefer to make some invite posts on my blog?
Whats up very cool site!! Man .. Excellent ..
Wonderful .. I’ll bookmark your web site and take the feeds also?
I’m satisfied to find so many useful info here within the
post, we need work out extra techniques on this regard,
thank you for sharing. . . . . .
I blog often and I truly thank you for your information. Your article has truly peaked my
interest. I’m going to book mark your site and keep
checking for new details about once a week.
I subscribed to your Feed too.
What’s up, I want to subscribe for this webpage to
obtain newest updates, so where can i do it please help out.
I need to to thank you for this very good read!!
I definitely loved every bit of it. I have got you book-marked to check out new things you post…
Heya are using WordPress for your blog platform?
I’m new to the blog world but I’m trying to get started and set up my
own. Do you require any coding knowledge to make your own blog?
Any help would be really appreciated!
Thank you for every other informative blog.
Where else may just I am getting that type of information written in such
a perfect way? I have a undertaking that I am simply now working on, and I have been at
the glance out for such info.
We are a group of volunteers and starting a new scheme
in our community. Your site offered us with valuable information to work
on. You’ve performed a formidable task and our whole neighborhood will probably be grateful to you.
Ahaa, its good conversation regarding this article at this place at this web site, I have
read all that, so at this time me also commenting at this place.
What’s up to every one, it’s actually a nice for me to pay a quick visit this web site, it includes
precious Information.
I will right away grasp your rss as I can’t to find your email subscription link or newsletter service.
Do you have any? Kindly permit me know so that I may subscribe.
Thanks.
There is definately a lot to know about this topic.
I like all of the points you have made.
Hey I know this is off topic but I was wondering if you knew of
any widgets I could add to my blog that automatically tweet my
newest twitter updates. I’ve been looking for a plug-in like this for quite some time
and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I
look forward to your new updates.
I believe this web site holds very good indited articles blog posts.