题目传送门: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
不得不说,这个题目真的是出得辣鸡,数据范围都没给全………
Very good info. Lucky me I found your website by chance (stumbleupon).
I’ve bookmarked it for later!
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
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..
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.
. . . . .
Greetings! Very useful advice in this particular post!
It’s the little changes that produce the most significant changes.
Thanks a lot for sharing!
I constantly spent my half an hour to read this webpage’s content all the time along with a mug of coffee.
It’s very straightforward to find out any topic on web as compared to books, as I found this article at this web site.
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.
. . . . .
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?
I get pleasure from, lead to I discovered exactly
what I used to be having a look for. You have ended my 4 day lengthy hunt!
God Bless you man. Have a great day. Bye
Hi there it’s me, I am also visiting this site daily, this web page is actually
good and the users are actually sharing pleasant thoughts.
I pay a quick visit everyday some websites and sites to read articles, except this webpage gives
quality based writing.
Good day! Would you mind if I share your blog with my zynga
group? There’s a lot of people that I think would really appreciate your content.
Please let me know. Thanks
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!
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!
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!
Now I am going to do my breakfast, after having my breakfast
coming yet again to read other news. natalielise plenty of fish
Right away I am ready to do my breakfast, once having my breakfast coming over again to read other news.
Heya i am for the first time here. I came across this board and I to find It truly useful & it helped me out much.
I’m hoping to present something again and help others like you
aided me. natalielise plenty of fish
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!
I think the admin of this web page is in fact working hard in favor of his web site, for the reason that here every data is quality
based material. natalielise pof
Link exchange is nothing else but it is just placing the other person’s weblog link on your page at
appropriate place and other person will also do similar
for you.
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.
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!
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
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!
Hello! I just would like to offer you a huge thumbs up for
the excellent information you have here on this post. I will be coming
back to your blog for more soon.
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.
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.
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!
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!
What a stuff of un-ambiguity and preserveness of valuable
know-how on the topic of unpredicted feelings.
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.
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
I enjoy, lead to I discovered just what I used to be having a look
for. You have ended my 4 day long hunt! God Bless you man. Have a great day.
Bye
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!
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.
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!
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!
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
My brother recommended I might like this website. He was totally right.
This post truly made my day. You can not imagine simply how much
time I had spent for this info! Thanks!
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.
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
Hi, this weekend is pleasant in support of me, because this point
in time i am reading this wonderful educational paragraph here
at my house.
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.
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
I constantly spent my half an hour to read this website’s articles
or reviews every day along with a mug of coffee.
whoah this blog is wonderful i like reading your posts.
Stay up the great work! You understand, many persons are hunting round for
this info, you can aid them greatly.
There is certainly a great deal to learn about this topic.
I love all of the points you’ve made.
What’s up, this weekend is good in support of me, for the reason that this point in time i am reading this wonderful educational piece of writing here at my home.
Thanks for finally talking about >【POJ 2891】Strange
Way to Express Integers – Qizy’s Database <Loved it!
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!
For newest news you have to visit world-wide-web and on world-wide-web I found this site
as a most excellent site for most up-to-date updates.
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
I am regular visitor, how are you everybody? This post posted at this website
is really nice.
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.
Incredible points. Sound arguments. Keep up the amazing spirit.
Hi, i think that i saw you visited my site so i came to “return the favor”.I am attempting to find things
to improve my website!I suppose its ok to use a few of your ideas!!
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!
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!
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
Good post. I will be dealing with a few of these issues
as well..
This post will help the internet viewers for setting up new weblog or even a
blog from start to end.
Outstanding story there. What occurred after? Take care!
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!
If you wish for to get much from this post then you have to
apply such strategies to your won website.
Regards for helping out, great information. “You must do the things you think you cannot do.” by Eleanor Roosevelt.
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!
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!
I need to to thank you for this fantastic read!! I definitely enjoyed
every little bit of it. I have got you book marked to look at new
stuff you post…
I’m not sure exactly why but this web site is loading incredibly slow for me.
Is anyone else having this problem or is it
a problem on my end? I’ll check back later on and see if the problem still exists.
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!
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!
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
If you are going for best contents like myself,
just pay a visit this site every day because it presents feature
contents, thanks
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!
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
I simply couldn’t depart your site before suggesting that I really loved the standard info a person provide for your visitors?
Is gonna be again steadily in order to investigate cross-check new posts
I used to be able to find good information from your blog posts.
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..