人啊，犹如流水。

Kuroba_kaito @ 2025-01-11 10:52:20

by dg114514 @ 2025-01-11 11:08:30

@Kuroba_kaito可过啊

by Kuroba_kaito @ 2025-01-11 11:09:05

@dg114514

请告诉我详细做法，你说的很乱。

by FBW2010 @ 2025-01-11 11:10:09

@dg114514 不是，你建n个树状数组修一次最劣 O(n\sqrt n\log n) 了阿

by dg114514 @ 2025-01-11 11:12:08

@Kuroba_kaito 首先预处理出 1 \sim n 的倍数，复杂度 O(n\log n)。然后建 n 棵树状数组，维护 a 的第 1 \sim n 的倍数个数，每次修改 \log n 个树状数组，总共 O(\log^2 n)（可能寄）

by dg114514 @ 2025-01-11 11:13:14

@FBW2010引理来自蓝书，\sum^n_{i=1} d(i) \sim n \log n

by Kuroba_kaito @ 2025-01-11 11:13:57

看到这句蚌埠住了。

by Kuroba_kaito @ 2025-01-11 11:14:31

@dg114514

你这和暴力没啥区别。

by dg114514 @ 2025-01-11 11:14:43

如果 d=1，维护一个 sum=\sum a（口胡的）

by FBW2010 @ 2025-01-11 11:15:05

@dg114514 但单个数因数依旧个数是 \sqrt n 的，如果一直修一个数就退化了

by rnf5114 @ 2025-01-11 11:15:09

@Kuroba_kaito题目是啥