【BZOJ 2393】Cirno的完美算数教室

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2393
数据生成器:http://paste.ubuntu.com/22548407/

额,容斥第一题,竟然成了乱搞…….
这题的时间复杂度是玄学……
就是搞出互质的baka数,然后容斥

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

const int MAXN = 2000;

int l,r,arr[MAXN],tmp[MAXN],vout,cnt,tot;

void DFS(LL w){
	if (w > r) return;
	tmp[++cnt] = w;
	DFS(w*10+2);
	DFS(w*10+9);
}

inline void prework(){
	DFS(2); DFS(9);
	sort(tmp+1,tmp+cnt); 
	for (int i=1,tag=0;i<=cnt;i++,tag=0) {
		for (int j=i-1;j;j--) if (tmp[i] % tmp[j] == 0) {tag = 1; break;}
		if (!tag) arr[++tot] = tmp[i];
	}
	for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

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

void solve(int step, int sz, int w){
	if (step == tot+1) {
		if (sz & 1) vout += r/w - (l-1)/w;
		else if (sz) vout -= r/w - (l-1)/w;
	} else {
		solve(step+1,sz,w);
		LL buf = (LL)w/GCD(w,arr[step])*arr[step];
		if (buf <= r) solve(step+1,sz+1,buf);
	}
}

int main(){
	scanf("%d%d",&l,&r);
	prework();
	solve(1,0,1);
	printf("%d\n",vout);
	return 0;
}

25 thoughts to “【BZOJ 2393】Cirno的完美算数教室”

  1. Hi! This is kind of off topic but I need some guidance from
    an established blog. Is it tough to set up your own blog?
    I’m not very techincal but I can figure things out pretty fast.
    I’m thinking about setting up my own but I’m not sure where to begin.
    Do you have any points or suggestions? With thanks

  2. I’m not that much of a internet reader to be honest but your blogs really nice, keep it up!
    I’ll go ahead and bookmark your site to come back later.
    All the best

  3. An impressive share! I’ve just forwarded this onto a co-worker who
    has been doing a little research on this. And he actually
    bought me lunch simply because I discovered
    it for him… lol. So allow me to reword this….
    Thanks for the meal!! But yeah, thanx for spending some time to
    talk about this topic here on your web site.

  4. You actually make it seem so easy together with your presentation but I
    to find this topic to be really something that I think I would never understand.
    It sort of feels too complex and very large
    for me. I’m taking a look forward to your next
    put up, I will attempt to get the grasp of
    it!

  5. Do you have a spam problem on this website; I also am a blogger, and I
    was wondering your situation; we have developed some nice practices and we
    are looking to swap techniques with others, be sure to shoot
    me an email if interested.

  6. When someone writes an post he/she retains the thought of a user in his/her brain that how a
    user can know it. Thus that’s why this article is
    amazing. Thanks!

  7. certainly like your web-site however you need to take a
    look at the spelling on quite a few of your posts.
    A number of them are rife with spelling issues and I find it very bothersome
    to inform the reality nevertheless I’ll surely come back again.

  8. Wow, marvelous blog layout! How long have you been blogging for?

    you made blogging look easy. The overall look of your website
    is great, let alone the content!

  9. It’s really a cool and helpful piece of information.
    I am happy that you simply shared this helpful info with us.

    Please stay us informed like this. Thanks for sharing.

  10. Howdy outstanding blog! Does running a blog like this require a large amount of work?
    I have virtually no understanding of programming however I
    had been hoping to start my own blog in the near future.
    Anyhow, should you have any ideas or tips for new blog owners
    please share. I understand this is off subject
    nevertheless I just had to ask. Thanks!

  11. Thanks for one’s marvelous posting! I truly enjoyed reading
    it, you can be a great author. I will be sure to
    bookmark your blog and will eventually come back at some point.
    I want to encourage that you continue your great job, have a nice evening!

  12. It’s actually a nice and useful piece of info. I am satisfied that you just
    shared this useful information with us. Please keep us informed like this.
    Thank you for sharing.

  13. Hello, i think that i saw you visited my web site thus i came to “return the
    favor”.I am trying to find things to enhance my site!I suppose its ok
    to use a few of your ideas!!

  14. Hey there! I know this is kind of off-topic but I needed to ask.
    Does operating a well-established blog such as yours require a massive
    amount work? I am brand new to operating a blog but I do write in my journal on a daily basis.
    I’d like to start a blog so I can easily share my own experience and feelings online.
    Please let me know if you have any suggestions or tips for
    brand new aspiring blog owners. Appreciate it!

  15. Woah! I’m really enjoying the template/theme of this site.
    It’s simple, yet effective. A lot of times it’s difficult to
    get that “perfect balance” between superb usability and visual appearance.
    I must say you have done a fantastic job with this.

    In addition, the blog loads extremely quick for me on Chrome.
    Exceptional Blog!

  16. Hey! This post couldn’t be written any better!
    Reading this post reminds me of my good old room mate!
    He always kept chatting about this. I will forward this post to him.
    Fairly certain he will have a good read. Thank you
    for sharing!

  17. Hello very cool blog!! Guy .. Beautiful .. Superb .. I’ll bookmark
    your site and take the feeds also? I’m happy
    to search out numerous helpful info here in the post,
    we’d like develop more techniques in this regard, thank you for
    sharing. . . . . .

Leave a Reply to sling tv Cancel reply

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