整除分块

wangyanjing · 2025-11-10 01:38:05 · 算法·理论

问题

给定一个正整数 n，

在 [1,n] 中的正整数 x，求：\lfloor\frac{n}{x} \rfloor 的不同的取值的数量。

结论

记：B = \lfloor \sqrt n \rfloor。

当 n \ge B(B+1) 时，Ans= 2B。
否则 Ans = 2B - 1。

证明

记：f(x) = \lfloor\frac{n}{x} \rfloor 。

• 假设有 $1 \le y_1 < y_2 \le B$ ，且 $f(y_1) = f(y_2) = k$。 $$\therefore \min(y_2) = y_1+1,\forall x \in[y_1,y_2] ,f(x) = k $$ $$\therefore \frac{n}{y_1 } -\frac{n}{y_1 + 1} < 1 \therefore \frac{n}{ (y_1+1)y_1} < 1 \therefore n < (y_1 + 1) y_1$$ $$\because y_1 < y_2\le B \therefore (y_1 (y_1 + 1)) _{\max} = B(B-1) \le n$$ 故假设不成立。 那么：当 $x \le B$ 时，每个 $f(x)$ 都不同，故对答案的贡献为 $B$。
• $$\because(\frac{n}{x} - \frac{n}{x+1})_{\max} = (\frac{n}{x(x+1)})_{\max} , (x(x+1))_{\min} = (B+1)(B+2) $$ $$ \therefore (\frac{n}{x} - \frac{n}{x+1})_{\max}= \frac{n}{(B+1)(B+2)} < 1$$ 所以 $f(x)$ 的取值单调不上升，而且 $f(x) - f(x+1) \le 1$。 由函数 $f$ 单调不上升可得：$ f(x) \le \lfloor \frac{n}{B+1} \rfloor $。 记：$R = \lfloor \frac{n}{B+1} \rfloor$。 由 $f(x) - f(x+1) \le 1$ 可得：$[1,R] $ 内 $f(x)$ 都能取到。 那么答案为 $R$。 - 当 $n \ge (B+1)B$ 时：$R = B$。 - 当 $n < (B+1)B$ 时：$R = B-1$。

考虑交界处，即是否存在 f(B) = f(B+1)。

• 当 n \ge (B+1)B 时：f(B) = B+1,f(B+1) = B。
• 当 n < (B+1)B 时：f(B) = B,f(B+1) = B-1。

故不存在 f(B) = f(B+1)。

证毕！

技巧

沿用：f(x) = \lfloor\frac{n}{x} \rfloor 。

对于一个 x，如果想找 y \ge x，且 f(x) = f(y)。

那么： y \in [x,f(f(x))] 。

证：

若 f(x) = f(y)，则：