[l, r]区间内有多少非平方数？

杂谈 1：论 \([l, r]\) 之间的非平方数 Part 0 例题 先看一道例题； 给定两个数 \(l, r\)，求 \(l \sim r\) 之间有多少个数不是平方数。平方数的定义：是一个数的平方。如 \(16\) 是平方数，因为 \(4^2 = 16\)，\(11\) 则不是，因为 \(\sqrt{11}\) 不为整数。数据范围：\(1 \le l, r \le 10^9\)。 有些人一看到题目就像：“这不纯暴力吗？”。是的，大多数人看到题目的第一直觉是暴力。但是随着 \(l, r\) 的增大，暴力算法会跑得很慢，下面介绍几种算法来解决这个问题。 Part 1 纯暴力 直接枚举 \([l, r]\) 区间，对于每个 \(i\) 判断 \(\sqrt{i} - \lfloor \sqrt{i} \rfloor\) 是否为 \(0\)。（因为平方数开根是整数）如果是，计数器 \(+1\)。最后输出 \(r - l + 1\) 减去计数器里的数即可。 代码； ll ans = 0; for (int i = l; i <= r; ++ i) { if (sqrt(i) - int(sqrt(i)) == 0) { ++ ans; } } cout << (r - l + 1) - ans << '\n'; 但是，这种算法的时间复杂度是 \(O(r - l + 1)\)。如果 \(r - l + 1\) 超过 \(10^8\) 会超时（注意，sqrt 函数也占用一定时间）。下面就介绍另一种算法。 Part 2 小暴力 这种算法属于暴力，但不是纯暴力。大概的思路就是：定义两个变量 \(A, B\)。从 \(l\) 开始，一个一个数枚举，找到 \([l, r]\) 之间的最小的平方数并存进 \(A\) 里。再从 \(r\) 开始，一个一个数枚举，找到 \([l, r]\) 之间的最大的平方数并存进 \(B\) 里。 如果两个都没找到（即 \(A = B = 0\))，答案为 \(r - l + 1\)（因为 \(A = B = 0\) 表示 \([l, r]\) 之间没有平方数），否则答案为 \((r - l + 1) - (B - A + 1)\)（序列长度减去区间平方数，读者可自证为什么 \(B - A + 1\) 是 \([l, r]\) 之间的平方数个数）。 代码： for (ll i = l; ; ++ i) { if (sqrt(i) - int(sqrt(i)) == 0) { A = sqrt(i); break; } } for (ll i = r; ; -- i) { if (sqrt(i) - int(sqrt(i)) == 0) { B = sqrt(i); break; } } if (!A && !B) { cout << r - l + 1 << '\n'; } else { cout << r - l + 1 - (B - A + 1) << '\n'; } 设离 \(l\) 最近的比 \(l\) 大的平方数是 \(A\)， 离 \(r\) 最近的比 \(r\) 小的平方数是 \(B\)，这种算法的时间复杂度是 \(O(A - l + r - B)\)。如果 \(A\) 离 \(l\) 太远或 \(B\) 离 \(r\) 太远就会 TLE。 Part 3 二分 我们可以发现，平方数满足单调性（\(1, 4, 9, 16, 25, 36, \cdots\)），所以可以二分。 \(\sqrt{10^9} ≈ 31622\)，我们可以构造一个 \(0 \sim 31622\) 的平方数数组（\(a_i = i^2\)）。因此，我们可以二分在数组里找答案。找一个 \(L\) 使得 \(L^2 \ge l\)，再找一个 \(R\) 使得 \(R^2 > r\)，答案就是 \(r - l + 1 - \max(0,\ R - L)\)（跟上个算法的思想差不多，读者可自证）。