【BZOJ 3930】[CQOI2015] 选数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3930
神犇题解:http://www.cnblogs.com/iwtwiioi/p/4986316.html

解题报告

这题,仔细想一想,岂不是跟这个题一样:http://oi.cyo.ng/?p=498
于是答案就是这个东西:$ \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m { \cdots \sum\limits_{k = 1}^m {[gcd(i,j, \cdots ,k) = K]} } } = \sum\limits_{i = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {\sum\limits_{j = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } { \cdots \sum\limits_{k = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {[gcd(i,j, \cdots ,k) = 1]} } } = \sum\limits_{d = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {\mu (d) \cdot {{\left\lfloor {\frac{m}{{Kd}}} \right\rfloor }^n}}$
于是剩下的锅就是预处理莫比乌斯函数的前缀和了!
然而我只会 $ O(n)$ 的做法,于是就跪了

PoPoQQQ大爷给了一种神奇的做法:http://blog.csdn.net/popoqqq/article/details/44917831
大概就是说,莫比乌斯函数的前缀和可以进行如下变换:
$ \sum\limits_{i = 1}^n {\mu (i) = 1 – \sum\limits_{i = 2}^n {(0 – \mu (i)) = } 1 – \sum\limits_{i = 2}^n {(\sum\limits_{j|i} {\mu (j)} – \mu (i))} = 1 – \sum\limits_{i = 2}^n {\sum\limits_{j|i,i \ne j} {\mu (j)} } } = 1 – \sum\limits_{j = 1}^n {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)} = 1 – \sum\limits_{j = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)}$
换一句话说,莫比乌斯函数的前缀和可以做到 $ O(\sqrt n \log n)$
这样的话,感觉复杂度是 $ O(n \log n)$ 的
然而PoPoQQQ大爷说,预处理前 $ S$ 个值的话,复杂度就可以变成:$ O(\frac{n}{S}\sqrt n lo{g_2}\frac{n}{S})$
然而并不知道怎么证明,感觉很有道理的样子!

当然这题还有容斥的做法
首先有结论:$ gcd(i,j) \le (r – l),(i,j \in (l,r))$
证明的话,参见这里:https://blog.sengxian.com/solutions/bzoj-3930
于是考虑 $ f(i)$ 表示gcd为i的方案数,则 $ f(i) = {\left\lfloor {\frac{m}{{Ki}}} \right\rfloor ^n} – \sum\limits_{i|j} {f(j)}$
这样的话, $ f(1)$ 就是答案辣!

—————————— UPD 2017.2.20 ——————————
突然发现,莫比乌斯函数的前缀和不是杜教筛的模板题吗?
当然PoPoQQQ的做法也有可取之处:不用复杂度公式推导

278 thoughts to “【BZOJ 3930】[CQOI2015] 选数”

  1. I am really loving the theme/design of your weblog.
    Do you ever run into any web browser compatibility problems?
    A small number of my blog audience have complained about my website
    not working correctly in Explorer but looks great in Firefox.
    Do you have any solutions to help fix this problem?

  2. Excellent pieces. Keep posting such kind of info on your blog.
    Im really impressed by it.
    Hey there, You’ve done a great job. I will certainly digg it
    and in my view recommend to my friends. I’m confident they will be benefited from this website.

  3. My brother suggested I might like this web site.
    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!

  4. I think this is one of the most vital information for me.
    And i’m glad reading your article. But want to remark on few general things, The website style is wonderful,
    the articles is really excellent : D. Good job, cheers

  5. We’re a group of volunteers and opening a new scheme in our community. Your website offered us with valuable information to work on. You have done an impressive job and our whole community will be thankful to you.

  6. Someone necessarily assist to make seriously posts I would state.

    This is the very first time I frequented your website page and
    so far? I surprised with the research you made to create this actual
    publish extraordinary. Magnificent process!

  7. My brother suggested I might like this blog. He was entirely right.

    This post actually made my day. You can not imagine simply how much time I had spent for this info!
    Thanks!

  8. Along with almost everything which appears to be developing within this subject matter, many of your opinions tend to be rather radical. Nevertheless, I appologize, but I can not give credence to your whole idea, all be it refreshing none the less. It would seem to us that your comments are not entirely validated and in actuality you are yourself not totally convinced of your assertion. In any event I did appreciate looking at it.

  9. Hey there just wanted to give you a quick heads up.The words in your content seem to be runningoff the screen in Chrome. I’m not sure if this is a formatting issueor something to do with web browser compatibility but I thought I’d post to letyou know. The design look great though! Hope you get the problem fixed soon. Kudos

  10. What i do not realize is in fact how you’re not really a lot more neatly-preferred than you may be right now. You are so intelligent. You understand thus significantly in relation to this topic, made me in my view consider it from so many numerous angles. Its like women and men don’t seem to be involved until it is one thing to accomplish with Woman gaga! Your own stuffs nice. All the time take care of it up!

  11. [url=http://phenergan24.com/]phenergan[/url] [url=http://femaleviagra2019.com/]female viagra[/url] [url=http://valtrex100.com/]buy generic valtrex online canada[/url] [url=http://propranolol100.com/]propranolol[/url] [url=http://advair2019.com/]buy advair[/url]

  12. How long does a copyright last on newspaper articles?. . If a service copies newspapers articles and then posts it in a database on the Internet, is there also a copyright on the Internet content?.

  13. Terrific article! That is the kind of info that are supposed to be shared across the internet. Shame on the seek engines for now not positioning this publish upper! Come on over and seek advice from my site . Thank you =)|

  14. After looking into a few of the blog articles on your web page, I really appreciate your technique of writing a blog. I added it to my bookmark website list and will be checking back soon. Please check out my web site as well and let me know how you feel.|

  15. Hey! Do you know if they make any plugins to assist with SEO? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results. If you know of any please share. Thank you!|

  16. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You obviously know what youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something enlightening to read?|

  17. I’m curious to find out what blog platform you are utilizing? I’m having some minor security issues with my latest site and I would like to find something more safeguarded. Do you have any solutions?|

  18. all the time i used to read smaller articles or reviews which as well clear their motive, and that is also happening with this paragraph which I am reading here.|

  19. Woah! I’m really digging the template/theme of this website. It’s simple, yet effective. A lot of times it’s challenging to get that “perfect balance” between superb usability and visual appearance. I must say that you’ve done a very good job with this. In addition, the blog loads very quick for me on Firefox. Excellent Blog!|

  20. I was suggested this web site through my cousin. I’m no longer certain whether this post is written by him as no one else recognize such detailed about my problem. You are wonderful! Thank you!|

  21. I don’t even know how I ended up here, but I thought this post was good.I do not know who you are but certainly you are going toa famous blogger if you are not already Cheers!

  22. This design is steller! You most certainly know how to keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Excellent job. I really enjoyed what you had to say, and more than that, how you presented it. Too cool!|

  23. Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!|

  24. I’m really inspired together with your writing talents as well as with the structure for your weblog. Is that this a paid subject or did you modify it your self? Anyway stay up the excellent high quality writing, it is uncommon to peer a great weblog like this one these days..|

  25. Good day! 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 subjects as yours and I think we could greatly benefit from each other. If you happen to be interested feel free to shoot me an e-mail. I look forward to hearing from you! Terrific blog by the way!|

  26. I’m really impressed along with your writing skills as well as with the layout on your blog. Is this a paid subject or did you customize it yourself? Anyway keep up the nice high quality writing, it’s uncommon to look a nice blog like this one today..|

Leave a Reply

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