题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2480
数据生成器：http://paste.ubuntu.com/23021720/
同2995
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
const double EPS = 1e-3;
const int MAXN = 100000;
int a,b,c;
namespace Hash{
const int MOD = 99971;
int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
inline void init(){memset(head,0,sizeof(head)); T=0;}
inline void insert(int v, int d) {
nxt[++T] = head[v%MOD];
val[T] = v; data[T] = d;
head[v%MOD] = T;
}
inline int query(int v){
for (int i=head[v%MOD];i;i=nxt[i])
if (val[i] == v) return data[i];
return -1;
}
};
inline int pow(int w, int t, int p){
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret*w % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}
int GCD(int a, int b) {return b?GCD(b,a%b):a;}
void EX_GCD(int a, int b, LL &x, LL &y) {
if (!b) x = 1, y = 0;
else EX_GCD(b,a%b,y,x), y -= a/b*x;
}
inline int EX_GCD(int a, int b, int pur){
LL ret,tmp; EX_GCD(a,b,ret,tmp);
return (ret*pur%b+b) % b;
}
inline void BSGS(){
int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c;
while ((tmp=GCD(a,c)) > 1)
if (b % tmp) {printf("No Solution\n"); return;}
else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;
for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;
Hash::init();
int lim = int(ceil(sqrt(c)) + EPS);
for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;}
else Hash::insert((LL)w*sta%c,i);
}
for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) {
tmp = Hash::query(EX_GCD(w,c,b)); //if (i == 1) cout<<w<<endl;
if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
}
printf("No Solution\n");
}
int main(){
while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
return 0;
}
Inspiring story there. What happened after? Thanks!
Thank you, I’ve just been looking for info approximately this subject for ages and
yours is the best I’ve came upon so far. But, what in regards to the bottom line?
Are you sure in regards to the supply?
I seriously love your site.. Pleasant colors & theme.
Did you make this website yourself? Please reply back
as I’m planning to create my very own blog and would like to
find out where you got this from or what the theme is
named. Kudos!
Hi, its fastidious paragraph regarding media print,
we all be aware of media is a wonderful source of facts.
If some one wishes to be updated with latest technologies therefore he must be visit this site
and be up to date all the time.
I do agree with all of the concepts you’ve presented in your post.
They’re really convincing and will definitely work. Nonetheless, the
posts are too brief for novices. May just you please lengthen them a bit from subsequent time?
Thanks for the post.
I am really inspired along with your writing talents as neatly as with the structure on your weblog.
Is that this a paid subject or did you customize it yourself?
Either way keep up the nice quality writing, it is
rare to see a great blog like this one today..
It’s going to be ending of mine day, however before end I am reading this wonderful paragraph to increase
my experience.
Great work! This is the kind of information that are meant to be shared across the internet.
Shame on Google for not positioning this publish upper!
Come on over and consult with my web site . Thank you =)
I got this web page from my pal who informed me
concerning this website and now this time I am browsing this
site and reading very informative articles at this time.
Excellent article. I’m experiencing many of these issues as well..
This is very interesting, You are a very skilled blogger.
I have joined your feed and look forward to seeking more of your great post.
Also, I’ve shared your site in my social networks!
Definitely believe that which you said. Your favorite justification seemed to be on the internet the
easiest thing to be aware of. I say to you, I definitely get
irked while people consider worries that they just do not know about.
You managed to hit the nail upon the top and also defined
out the whole thing without having side effect , people can take
a signal. Will probably be back to get more. Thanks
I know this site offers quality depending content and additional material, is there any other website which presents these kinds of
things in quality?
Hi! Someone in my Myspace group shared this website with us so I came to check
it out. I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers!
Great blog and great style and design.
I was looking through some of your posts on this internet site and I conceive this internet site is very informative ! Retain putting up.
I am sure this piece of writing has touched all the internet users, its really really fastidious
article on building up new webpage.
Have you ever considered about adding a little bit
more than just your articles? I mean, what you say is valuable and everything.
Nevertheless think about if you added some great graphics or videos to give your
posts more, “pop”! Your content is excellent but with pics and video clips, this website could undeniably be one of the greatest in its niche.
Great blog!
Hi, i think that i saw you visited my blog so i came to “return the
favor”.I am trying to find things to improve my website!I suppose its
ok to use some of your ideas!!
Nice post. I used to be checking constantly this blog and I’m
inspired! Very useful information specifically the closing part 🙂 I take care
of such information a lot. I used to be seeking this certain information for a very
long time. Thanks and good luck.
I was curious if you ever thought of changing the layout of your website?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having one or 2 images.
Maybe you could space it out better?
Way cool! Some extremely valid points! I appreciate
you penning this write-up and also the rest of the website is extremely good.
Thanks , I have just been searching for information approximately this subject for ages and yours is the best I’ve discovered so far.
However, what about the conclusion? Are you positive
concerning the supply?
It’s in reality a nice and useful piece of information. I am satisfied
that you shared this helpful info with us. Please keep us informed like this.
Thanks for sharing.
Have you ever considered publishing an e-book or guest authoring
on other blogs? I have a blog centered on the same information you discuss and would really like to have you
share some stories/information. I know my audience would value your work.
If you’re even remotely interested, feel free to send me
an e-mail.
Heya i am for the first time here. I found this board and I find It really useful
& it helped me out much. I hope to give something back and help
others like you aided me.
I just could not leave your site before suggesting that
I really enjoyed the usual information a person supply to your guests?
Is gonna be back continuously in order to investigate cross-check new posts
I’ll right away seize your rss feed as I can’t in finding your email
subscription hyperlink or e-newsletter service.
Do you have any? Kindly allow me recognise in order that I may just subscribe.
Thanks.
When someone writes an post he/she maintains the image
of a user in his/her brain that how a user can understand it.
Thus that’s why this article is amazing. Thanks!
Wow that was strange. I just wrote an really long comment but after I clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Regardless, just wanted to say fantastic blog!