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

$q$ 次询问，$1\leq n\leq 10^{18}$，$1\leq q\leq 10^5$。

对于一次询问，我们肯定可以直接暴力遍历所有的 $1\leq x\leq n$ 进行判断。

可以预处理，先把 $1$ 到 $10^6$ 都扫一遍，然后可以知道每个 $1\leq n\leq 10^6$ 的答案。

把答案存下来，每次询问即可 $\mathcal O(1)$ 回答。

时间复杂度 $\mathcal O(n+q)$。

这一档分虽然 $\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)$。

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)$。