【BZOJ 2242】[SDOI2011] 计算器

Qizy BSGS, 数论, 欧几里得算法, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2242
数据生成器：http://paste.ubuntu.com/22875643/
数据传送门：http://pan.baidu.com/s/1dE71QHr

这个题，做了一个下午+一个晚上，最后才发现是把”cannot”中间多加了一个‘a’
MD，老子好想杀人！ (╯‵□′)╯︵┻━┻

题目本身很简单，就是快速幂+拓展欧几里得+BSGS
但网上的程序，多少有问题，反正我能搜出来的，我都可以叉掉
我这份代码问题应该比较少吧：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 100000;
const double EPS = 1e-5;

namespace Hash{
	const int MOD = 99971;
	int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
	
	inline void init(){
		T = 0;
		memset(head,0,sizeof(head));
	}
	
	inline void insert(int w, int d){
		nxt[++T] = head[w%MOD];
		val[T] = w; data[T] = d;
		head[w%MOD] = T;
	}	
	
	inline int find(int w){
		for (int i=head[w%MOD];i;i=nxt[i])
			if (val[i] == w) return data[i];
		return -1;
	}
};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int quick_pow(int a,int b,int c){
	int ret = 1; while (b) {
		if (b & 1) ret = ((LL)ret * a) % c;
		a = (LL)a*a%c; b >>= 1;
	} return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, int &x, int &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 c) {
	int ret,tmp,gcd=GCD(a,b); 
	if (c%gcd) return -1;
	else {
		EX_GCD(a/gcd,b/gcd,ret,tmp);
		ret = (((LL)c/gcd*ret) % b + b) % b;
		return ret;
	}
}

inline void solve(int a, int b, int c) {
	int ret = EX_GCD(a,c,b); 
	if (~ret) printf("%d\n",ret);
	else printf("Orz, I cannot find x!\n");
}

inline void BSGS(int a, int b, int c) {
	Hash::init(); a %= c; b %= c;
	if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;}
	
	int lim = int(ceil(sqrt(c))+EPS);
	for (int i=0,w=1;i<=lim;i++) {
		if (w == b) {printf("%d\n",i); return;}
		Hash::insert(w,i);
		w = ((LL)w*a) % c;
	}
	
	int w_ori = quick_pow(a,lim,c), rev_ori = quick_pow(w_ori,c-2,c);
	for (int i=1,w=w_ori,rev=rev_ori;i<=lim;i++) {
		int tmp = Hash::find(((LL)rev*b) % c);
		if (tmp > -1) {printf("%d\n",i*lim+tmp); return;}
		w = ((LL)w*w_ori) % c;
		rev = ((LL)rev*rev_ori) % c;
	}
	printf("Orz, I cannot find x!\n");
}

int main(){
	int T=read(),ty=read(); while (T--) {
		int a=read(), b=read(), c=read();
		if (ty == 1) printf("%d\n",quick_pow(a,b,c));
		else if (ty == 2) solve(a,b,c);
		else BSGS(a,b,c);
	}
	return 0;
}

236 thoughts to “【BZOJ 2242】[SDOI2011] 计算器”

  22. Hi are using WordPress for your site platform?

    I’m new to the blog world but I’m trying to get started and create my
    own. Do you need any html coding expertise to make your own blog?
    Any help would be really appreciated!

    Reply

  32. Aw, this was a very good post. Finding the time and actual effort to produce a top notch article… but what can I say… I procrastinate a whole lot and don’t manage
    to get nearly anything done.

    Reply

  36. When I initially commented I clicked the “Notify me when new comments are added” checkbox and
    now each time a comment is added I get three e-mails
    with the same comment. Is there any way you can remove people from that service?
    Thanks a lot!

    Reply

  42. Thanks for ones marvelous posting! I definitely enjoyed reading it, you can be a great author.
    I will always bookmark your blog and will often come back later in life.
    I want to encourage you to continue your great posts, have a nice
    holiday weekend!

    Reply

  57. Hey very cool website!! Man .. Beautiful ..

    Wonderful .. I will bookmark your blog and take the
    feeds also? I’m glad to seek out so many helpful info
    here within the post, we’d like work out more techniques in this regard, thank you for sharing.
    . . . . .

    Reply

  65. Wonderful goods from you, man. I have remember your stuff previous to and you’re just extremely magnificent.
    I really like what you have got here, certainly like what you’re
    stating and the best way through which you are saying it.
    You’re making it enjoyable and you continue to take care of
    to keep it wise. I can not wait to read much more from you.
    That is really a terrific website.

    Reply

  74. Thank you for the auspicious writeup. It in fact was a amusement account it.
    Look advanced to more added agreeable from you!
    However, how can we communicate?

    Reply

  118. Everyone loves what you guys tend to be up too. This type of clever work and reporting!
    Keep up the terrific works guys I’ve you guys to my personal blogroll.

    Reply

  121. Just wish to say your article is as amazing. The clearness
    on your publish is just excellent and i can think you are an expert
    in this subject. Fine along with your permission let me to
    seize your RSS feed to stay up to date with drawing close post.
    Thank you one million and please continue the enjoyable work.

    Reply

  131. I know this if off topic but I’m looking into starting my own weblog and was curious what all is
    required to get set up? I’m assuming having a blog
    like yours would cost a pretty penny? I’m not very internet savvy so
    I’m not 100% positive. Any recommendations or advice would be greatly appreciated.
    Thank you

    Reply

  149. I really like what you guys tend to be up too.
    This sort of clever work and coverage! Keep up the very good works guys
    I’ve added you guys to blogroll.

    Reply

  151. We stumbled over here by a different page and thought I might as well
    check things out. I like what I see so now i am following you.
    Look forward to going over your web page for a second time.

    Reply

  177. Can I just say what a reduction to seek out someone who actually knows what theyre talking about on the internet. You undoubtedly know how one can convey a difficulty to gentle and make it important. Extra individuals must read this and perceive this facet of the story. I cant consider youre no more popular since you undoubtedly have the gift.

    Reply

  213. I’ve read some good stuff here. Certainly value bookmarking for revisiting. I surprise how much effort you put to make this type of excellent informative site.|

    Reply

  214. Thanks , I have recently been searching for info about this subject for a long time and yours is the greatest I’ve discovered so far. But, what concerning the bottom line? Are you positive about the supply?|

    Reply

  218. Hey There. I found your blog using msn. This is an extremely well written article. I will make sure to bookmark it and come back to read more of your useful information. Thanks for the post. I will certainly return.|

    Reply

  219. I blog frequently and I genuinely thank you for your content. This article has really peaked my interest. I’m going to bookmark your site and keep checking for new details about once per week. I opted in for your Feed too.|

    Reply

  220. Please let me know if you’re looking for a article author for your weblog. You have some really great posts and I think I would be a good asset. If you ever want to take some of the load off, I’d absolutely love to write some material for your blog in exchange for a link back to mine. Please send me an e-mail if interested. Kudos!|

    Reply

  228. What’s Taking place i am new to this, I stumbled upon this I’ve found It positively helpful and it has helped me out loads. I am hoping to give a contribution & aid different users like its helped me. Good job.|

    Reply

  232. Attractive portion of content. I simply stumbled upon your website and in accession capital to say that I acquire in fact enjoyed account your blog posts. Any way I will be subscribing to your augment and even I success you access persistently rapidly.|

    Reply

  235. First of all I want to say wonderful blog! I had a quick question in which I’d like to ask if you do not mind. I was interested to know how you center yourself and clear your thoughts prior to writing. I have had trouble clearing my mind in getting my ideas out there. I do take pleasure in writing however it just seems like the first 10 to 15 minutes are lost simply just trying to figure out how to begin. Any suggestions or tips? Cheers!|

    Reply

  236. We’re a group of volunteers and starting a new scheme in our community. Your site provided us with valuable info to work on. You have done an impressive job and our whole community will be thankful to you.|

    Reply

Leave a Reply to http://tinyurl.com/ Cancel reply

Your email address will not be published. Required fields are marked *