【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

相关链接

题目传送门: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;
}

34 thoughts to “【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek”

  1. I am actually happy to read this web site posts which contains tons of valuable data, thanks for providing these kinds of information.

  2. 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.

  3. 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.

  4. 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!

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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!

  10. 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!

  11. 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!

  12. 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.

  13. 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.

  14. 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.

  15. 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!

Leave a Reply

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