【POJ 2891】Strange Way to Express Integers

题目传送门:http://poj.org/problem?id=2891

这个东西,不保证互质,所以中国剩余定理上不了
于是就得合并方程:
把\(\left\{ \begin{array}{l}
x \equiv {a_1}(Mod{\rm{ }}{b_1})\\
x \equiv {a_2}(Mod{\rm{ }}{b_2})
\end{array} \right.\)
替换成\(x \equiv {a_1} + A \cdot {b_1}(Mod{\rm{ }}\frac{{{b_1} \cdot {b_2}}}{{GCD({b_1},{b_2})}})\)
其中A为\(A \cdot {b_1} – B \cdot {b_2} = {a_2} – {a_1}\)的最小非负整数解
至于推导过程嘛,就自己推一推咯,不想写latex了,太费时间

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

inline LL read(){
	char c=getchar(); LL 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;
}

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

LL EX_GCD(LL a, LL b, LL &x, LL &y){
	if (!b) {x=1;y=0;}
	else {EX_GCD(b,a%b,y,x);y-=a/b*x;}
}

inline LL EX_GCD(LL a, LL b, LL pur){
	LL ret,tmp; EX_GCD(a,b,ret,tmp);
	return ((ret*pur)%b + b) % b;
}

int main(){
	int n; while (~scanf("%d",&n)) {
		LL b1=read(),a1=read(),a2,b2,tag=0,A,tmp,gcd;
		for (int i=1;i<n;i++) {
			b2 = read(); a2 = read(); gcd = GCD(b1,b2);
			if (!tag) {
				if ((a2-a1)%gcd) tag = 1, printf("-1\n");
				else { 
					A = EX_GCD(b1/gcd,b2/gcd,(a2-a1)/gcd);
					a1 = a1 + (A*b1);
					b1 = b1/gcd*b2; a1 %= b1;
				}
			}
		}
		if (!tag) printf("%lld\n",((a1%b1)+b1)%b1);
	}
	return 0;
} 

另外,这个题,貌似会爆long long,不过只要你的代码跟我的差不多,就能过QAQ
不得不说,这个题目真的是出得辣鸡,数据范围都没给全………

80 thoughts to “【POJ 2891】Strange Way to Express Integers”

  1. Hello just wanted to give you a quick heads up. The text
    in your article seem to be running off the screen in Ie.
    I’m not sure if this is a formatting issue or something to
    do with web browser compatibility but I figured I’d post to let you know.
    The design look great though! Hope you get the issue resolved soon. Kudos

  2. I am extremely inspired along with your writing skills as neatly as with the layout for your blog.
    Is this a paid subject matter or did you customize
    it your self? Either way stay up the nice quality writing, it is rare to peer a great weblog like this one these days..

  3. Whats up very cool site!! Guy .. Excellent ..
    Superb .. I will bookmark your website and take the feeds additionally?
    I’m satisfied to search out numerous useful information here in the publish,
    we’d like work out more techniques on this regard, thank you for sharing.
    . . . . .

  4. Good day very nice blog!! Guy .. Excellent .. Superb ..
    I will bookmark your website and take the feeds also? I am glad to seek out numerous
    useful information here in the post, we want develop
    more strategies in this regard, thank you for sharing.
    . . . . .

  5. fantastic issues altogether, you simply received a new reader.

    What might you recommend in regards to your submit that you simply made some days ago?
    Any sure?

  6. Hello superb website! Does running a blog such as this take a
    massive amount work? I’ve absolutely no knowledge of coding but I had been hoping to start my
    own blog soon. Anyhow, if you have any ideas or
    techniques for new blog owners please share.

    I know this is off subject however I simply needed to ask.
    Thank you!

  7. Hey there, I think your website might be having browser compatibility issues.

    When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that,
    wonderful blog!

  8. Hello! I know this is kinda off topic nevertheless I’d figured I’d ask.
    Would you be interested in exchanging links or maybe guest writing
    a blog post or vice-versa? My website goes over a lot
    of the same topics as yours and I believe we could greatly
    benefit from each other. If you’re interested feel free to send me an e-mail.
    I look forward to hearing from you! Awesome blog by
    the way!

  9. Do you mind if I quote a few of your articles as
    long as I provide credit and sources back to your weblog?

    My blog is in the very same area of interest as yours and
    my visitors would genuinely benefit from some of the
    information you provide here. Please let
    me know if this okay with you. Appreciate it!

  10. I’m not sure why but this weblog is loading very slow for me.

    Is anyone else having this issue or is it a problem on my end?
    I’ll check back later on and see if the problem still exists.

  11. Hi terrific blog! Does running a blog similar to this
    take a massive amount work? I’ve very little understanding of coding however I had been hoping to start my own blog soon. Anyhow, should you have any ideas or techniques for new blog owners please share.
    I understand this is off subject nevertheless I just had to ask.
    Thanks a lot!

  12. I love your blog.. very nice colors & theme. Did you design this website yourself or did you hire someone to do
    it for you? Plz respond as I’m looking to construct my own blog and would
    like to know where u got this from. thanks

  13. When someone writes an piece of writing he/she retains the thought of a user in his/her
    mind that how a user can understand it. Therefore that’s
    why this article is outstdanding. Thanks!

  14. Heya i’m for the first time here. I found this board and I find It truly useful & it helped
    me out much. I hope to give something back and help
    others like you aided me.

  15. Howdy! Someone in my Myspace group shared this website with us so I came to check it
    out. I’m definitely enjoying the information.
    I’m bookmarking and will be tweeting this to my followers!
    Exceptional blog and excellent style and design.

  16. I absolutely love your site.. Very nice colors & theme.
    Did you create this website yourself? Please reply back as I’m hoping to create my very own blog and would love to know where you
    got this from or just what the theme is called.
    Many thanks!

  17. Hi! I’m at work browsing your blog from my new iphone 3gs!
    Just wanted to say I love reading through your blog and look forward to all your
    posts! Keep up the fantastic work!

  18. Hi, Neat post. There’s an issue with your website in internet explorer, might test
    this? IE still is the marketplace leader and a large component to people will miss your fantastic writing
    because of this problem.

  19. I just could not leave your web site prior to suggesting that I extremely enjoyed the standard
    info a person supply in your visitors? Is gonna be again often to inspect new
    posts

  20. Have you ever thought about adding a little bit more
    than just your articles? I mean, what you say
    is valuable and all. But think about if you added some great graphics or video
    clips to give your posts more, “pop”! Your content is excellent but
    with pics and clips, this blog could undeniably be one of the
    best in its niche. Excellent blog!

  21. Its like you read my mind! You seem to know so much about this, like you wrote the book in it
    or something. I think that you can do with a few pics to drive the message home a little bit, but other than that, this is excellent blog.
    A great read. I’ll certainly be back.

  22. Hi! I’ve been following your web site for a while now and
    finally got the bravery to go ahead and give you a
    shout out from Atascocita Tx! Just wanted to say keep up the good work!

  23. Yesterday, while I was at work, my sister stole my iphone
    and tested to see if it can survive a 40 foot drop, just so she can be a youtube sensation. My apple ipad is now destroyed and
    she has 83 views. I know this is completely off topic
    but I had to share it with someone!

  24. I do not know if it’s just me or if everyone else experiencing
    issues with your website. It appears as if some of the written text within your content are running off the
    screen. Can someone else please comment and let me know if this is happening to them as well?
    This may be a problem with my web browser because I’ve had this happen previously.
    Thanks

  25. I am no longer positive the place you are getting your info,
    but good topic. I must spend a while learning more or understanding more.
    Thanks for fantastic information I was looking for this information for my mission.

  26. I feel that is one of the most significant info for me.
    And i am glad studying your article. But wanna observation on some normal
    issues, The web site taste is great, the articles
    is really great : D. Just right activity, cheers

  27. Its like you read my mind! You appear to know a lot about this, like you wrote the book in it or something.
    I think that you could do with a few pics to drive the message home a little
    bit, but other than that, this is great blog.
    A fantastic read. I will certainly be back.

  28. I know this if off topic but I’m looking into starting my own blog and was wondering what all is required to get setup?
    I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web smart so I’m not 100% positive.
    Any recommendations or advice would be greatly appreciated.
    Many thanks

  29. Woah! I’m really digging the template/theme of this blog.
    It’s simple, yet effective. A lot of times it’s
    difficult to get that “perfect balance” between usability and visual appearance.
    I must say you’ve done a amazing job with this. Additionally,
    the blog loads extremely fast for me on Chrome.
    Exceptional Blog!

  30. Unquestionably consider that that you stated. Your favourite
    justification appeared to be on the internet the easiest factor to remember of.
    I say to you, I certainly get irked at the same time as folks think about worries that they plainly do not recognize about.

    You managed to hit the nail upon the highest and defined
    out the whole thing without having side effect , people could take a signal.
    Will likely be back to get more. Thanks

  31. Hi there! I know this is kind of off topic but I was wondering which blog platform are you
    using for this site? I’m getting tired of WordPress because I’ve had
    issues with hackers and I’m looking at alternatives for another platform.

    I would be awesome if you could point me in the direction of a good platform.

  32. It’s appropriate time to make some plans for the future and it is time to be happy.
    I have read this post and if I could I wish to suggest you some interesting things or suggestions.
    Perhaps you could write next articles referring to this article.
    I desire to read even more things about it!

  33. Wow that was strange. I just wrote an very long comment but after I
    clicked submit my comment didn’t show up. Grrrr…
    well I’m not writing all that over again. Anyhow, just wanted to
    say great blog!

  34. I get pleasure from, lead to I found just what
    I was taking a look for. You have ended my 4 day long hunt!
    God Bless you man. Have a great day. Bye

  35. I do not even know how I ended up here, but I thought this post was great.
    I do not know who you are but definitely you’re
    going to a famous blogger if you are not already 😉 Cheers!

  36. Howdy, I believe your blog might be having browser compatibility problems.
    Whenever I take a look at your site in Safari, it looks fine however when opening in IE,
    it’s got some overlapping issues. I just wanted to give you a quick heads up!
    Aside from that, wonderful blog!

  37. Howdy! Do you know if they make any plugins to assist with Search Engine Optimization?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good success.
    If you know of any please share. Kudos!

  38. I like the helpful info you provide in your articles.
    I’ll bookmark your weblog and check again here regularly.
    I am quite sure I’ll learn many new stuff right here!
    Best of luck for the next!

  39. Exceptional post however I was wanting to know if you could write a litte more on this subject?
    I’d be very grateful if you could elaborate a little bit more.

    Kudos!

  40. I love your blog.. very nice colors & theme.
    Did you create this website yourself or did you hire someone to do
    it for you? Plz reply as I’m looking to construct my own blog and would like to know where u got this from.
    many thanks

  41. Good day! I could have sworn I’ve been to this blog
    before but after checking through some of the post I realized it’s new to
    me. Nonetheless, I’m definitely happy I found it and I’ll be
    book-marking and checking back often!

  42. This is really fascinating, You are an overly professional blogger.

    I’ve joined your rss feed and look forward to in the hunt for more
    of your wonderful post. Also, I have shared your website in my social networks

  43. You have remarked very interesting details! ps nice site. “High school is closer to the core of the American experience than anything else I can think of.” by Kurt Vonnegut, Jr..

Leave a Reply

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