链接
题目传送门: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))的?
Hello! I just would like to give a huge thumbs up for the great info you have here on this post. I will be coming back to your blog for more soon.
As I website possessor I conceive the content material here is rattling good, appreciate it for your efforts.