不能这么算吧……然而我也不敢说EA说的是错的（
by FZzzz @ 2020-04-20 13:58:45
@[FZzzz](/user/174045) 那应该是啥啊
by EternalAlexander @ 2020-04-20 13:59:20
@[Narcissusany](/user/328040) 但你对这 $\sqrt n$ 种的每种取值都要做一遍 $\sqrt n$ 的整除分块不是吗
by EternalAlexander @ 2020-04-20 14:00:02
没做过这题，但大概看了下题解，应该是$O(n)$的
by PrincessQi @ 2020-04-20 14:01:02
小常数$O(n)$？
by PrincessQi @ 2020-04-20 14:01:29
我觉得吧是不是应该换个思路去证明有用的状态只有 $\sqrt n$ 个。~~但是没做过，也并不会。~~
by pomelo_nene @ 2020-04-20 14:03:00
@[SyadouHayami](/user/184977) 有用的状态确实是 $\sqrt n$，但是转移复杂度是 $\sqrt n$ 啊
by EternalAlexander @ 2020-04-20 14:03:50
@[alpha1022](/user/75840) 啊，您仔细看了这个题解吗。题解里两次整除分块都是对 $n$ 做的吧
by EternalAlexander @ 2020-04-20 14:09:21
第一篇题解在 $n=10^9$ 的情况下进行了 `1880979031750` 次运算。。。但是过了就很迷
by pomelo_nene @ 2020-04-20 14:26:05
@[EternalAlexander](/user/48355) 抱歉，刚才没仔细看是我的不对
请问题解是对 $\displaystyle\left\lfloor\frac nx\right\rfloor$ 做整除分块之后再对 $\displaystyle\left\lfloor\frac n{tx}\right\rfloor$ 做整除分块吗 qwq
by Aleph1022 @ 2020-04-20 14:31:06