数学(算法)

整除分块#

这个 $D_n$ 就是所有可能的取值集合 相关性质:

1. |$D_n$| $\leq$ 2$\sqrt{n}$
2. 每一个块的左右端点,$l=\lfloor \frac{n}{d+1} \rfloor +1 \leq i \leq \lfloor \frac{n}{d} \rfloor$

相关实现: 枚举每一个整除分块($D_i$)$的区间

1
 for(int l = 1; l <= n; l = r + 1){
2
        int cnt = (n / l);
3
        if(cnt < k) break;
4
        r = (n / cnt);
5
    }