Orrrrrzzzz! 唯膜而已quq。白学了杜教筛还能来解这个...

杜教筛求SG函数不好吗，时间复杂度$O(n^{\frac{3}{4}})$
SG函数首题留念！

终于推掉了。。

OMG!!!哈希大法好可怕啊……前面我说的那个二分查找结构只要改成一个哈希链表结构就可以随便做啦！复杂度直接去掉一个log，变成了$T(N) = \sum_{i=1}^{\sqrt{N}} (\sqrt{\frac{N}{i}} + \sqrt{i} ) × \frac{N}{P}$

我可能姿势哪里不太对，低空卡时卡过。感谢@Asm.Def 神犇的悉心指导

maya 这个结论居然是对的………
UPD…………写了个$T(N) = \sum_{i=1}^{\sqrt{N}} (\sqrt{\frac{N}{i}} + \sqrt{i} ) log N$的奇怪的东西……其实是卡不进时限的，我先把时限改成2s测了一下，最大数据1.6秒多…… 这里贴一下代码
UPD2…………比较科学的做法是用单调性预处理然后用二分查询= =话说为什么要在和我的UID相同的PID上放这道题……= =
UPD3：全套题解：http://www.cnblogs.com/Asm-Definer/p/4466729.html

回复 @Asm.Def :
Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

这个是出题人的标程