题解：P14304 【MX-J27-T1】分块

· · 题解

A. 分块

题意

给定 n，询问有多少个 1\leq x\leq n 满足 \lfloor\sqrt{x}\rfloor 是 x 的因子。

## 部分分 40 对于一次询问，我们肯定可以直接暴力遍历所有的 $1\leq x\leq n$ 进行判断。 可以预处理，先把 $1$ 到 $10^6$ 都扫一遍，然后可以知道每个 $1\leq n\leq 10^6$ 的答案。 把答案存下来，每次询问即可 $\mathcal O(1)$ 回答。 时间复杂度 $\mathcal O(n+q)$。 ## 部分分 50 这一档分虽然 $\mathcal O(n)$ 做不了了，但是 $\mathcal O(\sqrt n)$ 是可行的。 令 $k=\lfloor\sqrt{x}\rfloor$，我们可以枚举 $k$。 对于一个 $k$，考虑它会给哪些 $x$ 产生贡献。 注意到一定是形如 $x=k(k+c)$ 的形式才会被 $k$ 带来贡献。 具体的，由于 $k(k+3)=k^2+3k$ 而 $(k+1)^2=k^2+2k+1$，因为有 $k\geq 1$ 所以 $k(k+3)\geq (k+1)^2$。 也就是说，$\lfloor\sqrt{k(k+3)}\rfloor\neq k$。 因此，枚举 $k$，计算多少个 $x=k^2,x=k(k+1),x=k(k+2)$ 在 $[1,n]$ 之间。 时间复杂度 $\mathcal O(q\sqrt n)$。 ## 满分 100 50 分的做法，存在一个关键性质：只有 $x=k^2,x=k(k+1),x=k(k+2)$ 这三类形式的 $x$。 而显然，如果存在 $x=k^2$，则 $[1,n]$ 一定存在 $x=(k-1)^2$。其他两种同理。 因此，我们只关心最大的 $x=k^2$ 的 $k$ 是多少。剩下的 $1\leq k'\leq k$ 都一定合法。 直接计算 $m=\sqrt{n}$，则形如 $x=k^2$ 的有 $m$ 个。 同理可以计算出 $x=k(k+1)$ 和 $x=k(k+2)$ 形式的数的个数。 具体实现在 $m$ 周围往下枚举若干个，即可知道精确的 $x=k(k+1)$ 的数的个数，或使用二分搜索同理。 实现的时候，如果需要开根号，想要调用 $\textcolor{blue}{\texttt{sqrt(n)}}$，需要注意，对于 $\textcolor{blue}{\texttt{long long}}$ 类型应该使用 $\textcolor{blue}{\texttt{sqrtl(n)}}$，否则会产生精度误差导致挂分。这是因为 $\textcolor{blue}{\texttt{sqrt()}}$ 只在 $\textcolor{blue}{\texttt{double}}$ 精度范围内，而 $\textcolor{blue}{\texttt{sqrtl()}}$ 在 $\textcolor{blue}{\texttt{long double}}$ 精度范围内。$\textcolor{blue}{\texttt{double}}$ 的精度范围内无法精确表示 $\textcolor{blue}{\texttt{long long}}$ 类型。 依据实现时间复杂度为 $\mathcal O(q)$ 或 $\mathcal O(q\log n)$。