【BZOJ 3834】[Poi2014] Solar Panels

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3834
神犇题解:http://blog.csdn.net/popoqqq/article/details/42646823

题解

考虑我们枚举最后的gcd是A
如果成立,那么(min-1)/A != max/A

然后想一想莫比乌斯反演的题目
发现这货只会有O(sqrt(n))个拐点
就是下底函数分块

于是暴力枚举即可
用个Hash复杂度就是O(q*sqrt(n))的?

2 thoughts to “【BZOJ 3834】[Poi2014] Solar Panels”

Leave a Reply

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