题目传送门: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; }
Highly descriptive post, I liked that bit. Will there be a part 2?
Thanks for sharing your thoughts. I truly appreciate your efforts and I am waiting for your further
write ups thank you once again.
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
Wonderful blog! I found it while searching on Yahoo News.
Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while
but I never seem to get there! Thanks
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
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.
If some one needs expert view about running a blog then i suggest him/her to
visit this blog, Keep up the good work.
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!
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.
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!
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.
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!
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.
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!
Stunning quest there. What occurred after? Thanks!
Incredible story there. What happened after? Good luck!
Pretty! This has been a really wonderful article.
Thanks for supplying this info.
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!
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.
Heya! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing months of hard work due to no back up.
Do you have any methods to prevent hackers?
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!!
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!
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!
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!
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. . . . . .