相关链接
题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_f
解题报告
我们写出使答案最大且值最小的序列,不难发现这是一个斐波那契数列
进一步发现,这条主链的每一个点只会引申出一条支链,且支链不会再分
所以我们可以暴力算出了$\log n$条链,共$\log ^ 2 n$对数,然后暴力算贡献
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 1000000007; const int LOG = 100; vector<pair<LL, LL> > num[LOG]; inline LL read() { char c = getchar(); LL ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void solve(LL A, LL B) { if (A < num[2][0].first || B < num[2][0].second) { printf("1 %d\n", A * B % MOD); return; } for (int i = 2; i < LOG; i++) { if (A < num[i + 1][0].first || B < num[i + 1][0].second) { int cnt = 0; for (int j = 0; j < (int)num[i].size(); j++) { LL a = num[i][j].first, b = num[i][j].second; cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD; cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD; } printf("%d %d\n", i, cnt); return; } } } inline void prework() { num[0] = vector<pair<LL,LL> >{make_pair(1, 1)}; for (int i = 1; i < LOG; i++) { for (int j = 0; j < (int)num[i - 1].size(); ++j) { LL a = num[i - 1][j].first, b = num[i - 1][j].second; num[i].push_back(make_pair(b, a + b)); } LL a = num[i - 1][0].first, b = num[i - 1][0].second; num[i].push_back(make_pair(a + b, 2 * a + b)); } } int main() { prework(); for (int T = read(); T; T--) { LL A = read(), B = read(); solve(min(A, B), max(A, B)); } return 0; }
楼下是疯子。哈哈
I am actually happy to read this web site posts which contains tons of valuable data, thanks for providing these kinds of information.
Wow, this post is good, my younger sister is analyzing these kinds of things, therefore
I am going to inform her.
Asking questions are actually fastidious thing if you are
not understanding something fully, however this piece of writing offers
pleasant understanding yet.
Excellent pieces. Keep writing such kind of info on your page.
Im really impressed by your site.
Hi there, You’ve performed a fantastic job.
I will certainly digg it and personally suggest
to my friends. I am confident they will be benefited from this site.
Incredible points. Solid arguments. Keep up the
good work.
Hello Dear, are you truly visiting this web page daily, if so afterward you will without doubt take good know-how.
Heya i am for the first time here. I came across this board and I
find It truly useful & it helped me out a lot. I hope to give something back and help others like you aided me.
Greate article. Keep posting such kind of info on your blog.
Im really impressed by it.
Hi there, You have performed an excellent job.
I’ll certainly digg it and personally suggest to my friends.
I am sure they’ll be benefited from this web site.
Pretty! This has been a really wonderful post. Many thanks for providing
this information.
It’s the best time to make some plans for the future and it’s time to be happy.
I’ve read this submit and if I may just I want to suggest you some attention-grabbing things or tips.
Perhaps you can write subsequent articles relating to this article.
I wish to read even more things about it!
Hi colleagues, its wonderful post regarding educationand completely defined,
keep it up all the time.
For the reason that the admin of this web page is working, no hesitation very
shortly it will be well-known, due to its quality contents.
Hi to every one, the contents existing at this site are in fact
awesome for people knowledge, well, keep up the good work fellows.
I believe everything posted was actually very logical.
But, what about this? suppose you added a little content?
I am not saying your information is not good., but suppose you added a
title that grabbed folk’s attention? I mean 【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek – Qizy's Database
is kinda vanilla. You could glance at Yahoo’s front page and watch how they create post headlines to grab viewers to open the links.
You might add a video or a related picture or two to get
readers excited about what you’ve got to say.
In my opinion, it could make your blog a little bit more interesting.
Thank you for any other informative web site. The place else could I get that kind of info written in such an ideal method?
I have a project that I am simply now operating on, and I’ve been at the look out for
such info.
Awesome things here. I am very glad to look your post.
Thanks a lot and I am having a look ahead to touch you.
Will you please drop me a mail?
I know this site provides quality depending articles and additional material, is there any other web site which provides these data in quality?
Hmm it looks like your site ate my first comment (it was super long) so I guess
I’ll just sum it up what I had written and say,
I’m thoroughly enjoying your blog. I as well am an aspiring blog writer but I’m still
new to everything. Do you have any tips and hints for inexperienced blog
writers? I’d definitely appreciate it.
I saw a lot of website but I conceive this one holds something special in it in it
Excellent post. I used to be checking continuously this weblog and I am inspired!
Extremely useful info particularly the closing section 🙂 I care for
such info much. I used to be seeking this certain information for a long time.
Thanks and good luck.
Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your weblog?
My blog site is in the very same niche as yours and my visitors would truly benefit from some of the information you provide here.
Please let me know if this okay with you. Appreciate it!
My spouse and I absolutely love your blog and find a lot of your post’s to be just what I’m looking for.
Do you offer guest writers to write content for yourself?
I wouldn’t mind producing a post or elaborating on a number of the subjects
you write about here. Again, awesome blog!
Yes! Finally someone writes about sling tv.
Quality articles is the key to attract the people to pay a visit the
site, that’s what this web site is providing.
Hey there! Someone in my Facebook group shared this site with us so I
came to look it over. I’m definitely loving the information. I’m bookmarking
and will be tweeting this to my followers! Superb blog and great style and design.
I do not even know how I stopped up here, but I believed
this post was good. I don’t recognize who you are but definitely you’re going to a famous
blogger when you are not already. Cheers!
Thanks for any other wonderful post. The place else may anybody
get that kind of information in such an ideal
way of writing? I have a presentation subsequent week, and I am on the look for such information.
An impressive share! I’ve just forwarded this onto a friend who has been conducting a little homework on this.
And he in fact ordered me dinner because
I stumbled upon it for him… lol. So let me reword this….
Thanks for the meal!! But yeah, thanx for spending time to talk about this subject here on your website.
Aw, this was an exceptionally good post. Taking a few minutes and actual effort to make a
very good article… but what can I say… I put things off a
lot and don’t seem to get anything done.
I visited many websites except the audio feature for audio
songs present at this website is genuinely superb.
Wonderful post however I was wanting to know if you could write a litte more on this topic? I’d be very thankful if you could elaborate a little bit further. Bless you!
Very neat blog post. Want more.
Major thankies for the blog.Thanks Again. Fantastic.