这题的纯正暴力其实可以达到 60 分。。。。
先让我自己胡诌一个定义：
对于一个正整数 (x=k^2p)，(k) 尽量大且不为一（这里不把 1 算进去），称 (k^2) 为 (x) 的最大完全平方因子，此时 (p) 称为 (x) 的平方余数。
将数拆成 (a^2b(mu(b) e0)) 的形式，将 (b) 相同的放到一起，这一堆数的贡献就是这些数的个数减一。
答案等价于区间长度减去出现的不同的 (b) 的个数。
考虑 (l=1) 时的情况：
我们发现 (l=1)，如果 (a^2b(a e 1)) 在区间中，则 (b) 必在区间中，即贡献来自有完全平方因子的数，所以答案为有完全平方因子的数的个数。
这个东西不是很好求，我们改成求无完全平方因子的数的个数，用总数即区间长度减去它即可。
直观的式子长这样：（式子一）
[largesum_{i=1}^nmu^2(i)
]
考虑转换式子：（式子二）
[large
egin{aligned}
&sum_{i=1}^nmu^2(i)\
&=sum_{a^2ble n}[a=1][mu(b)
e0]\
&=sum_{a^2ble n}[mu(b)
e0]sum_{imid a}mu(i)\
&=sum_{i=1}^nmu(i)sum_{j=1}^{leftlfloorfrac{n}{i^2}
ight
floor}1\
&=sum_{i=1}^nmu(i)leftlfloorfrac{n}{i^2}
ight
floor\
&=sum_{i^2le n}mu(i)leftlfloorfrac{n}{i^2}
ight
floor
end{aligned}
]
复杂度不会算的说 /kk ((O(能过))？？？)
那么如果 (l e1) 呢？
直接差分肯定不行，比如 ({2,8,18,32,50},l=9)，差分结果是 (3)，正确答案是 (2)。
我们可以枚举一个数 (k)，计算区间 (left[frac{l-1}{k^2}, frac{r}{k^2} ight]) 内出现的无完全平方因子的数的个数即可。
#include <bits/stdc++.h>
#define int long long
#define N 10000010
using namespace std;
template <typename T>
inline void read (T &a) {
T x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
(ch == '-') and (f = 0);
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + (ch xor '0');
ch = getchar ();
}
a = f ? x : -x;
}
template <typename T, typename ...A>
inline void read (T &t, A &...a) {
read (t), read (a...);
}
template <typename T>
inline void print (T x) {
if (x < 0) putchar ('-'), x = -x;
if (x > 9) print (x / 10);
putchar (x % 10 + '0');
}
int mu[N], sum[N], sum_s[N], pri[N], cnt;
bitset <N> v;
inline void phigros (int n) {
mu[1] = sum[1] = sum_s[1] = 1;
for (int i = 2; i <= n; i++) {
(! v[i]) and (pri[++cnt] = i, mu[i] = -1);
for (int j = 1; j <= cnt and i * pri[j] <= n; j++) {
v[i * pri[j]] = 1;
if (! (i % pri[j])) break;
mu[i * pri[j]] = -mu[i];
}
sum[i] = sum[i - 1] + mu[i];
sum_s[i] = sum_s[i - 1] + mu[i] * mu[i];
// 处理平方前缀和，即式子一
}
}
inline int Min (int a, int b) {return a < b ? a : b;}
int mid;
inline int sol (int n) {
if (n < mid) return n - sum_s[n];
// 直接用式子一，这句特判 l < sqrt(r) 的情况
int k = sqrt (n), res = 0;
for (int i = 2, j = 0; i <= k; i = j + 1) {
j = Min (k, (int) sqrt (n / (n / i / i)));
res -= (sum[j] - sum[i - 1]) * (n / i / i);
}
// 式子二，数论分块做
return res;
}
int num, swa, swb, l, r, ans;
signed main () {
read (l, r);
mid = sqrt (r);
phigros (mid);
// 预处理 sqrt(r)，也只需要这么多
l--, num = l;
ans = sol (r) - sol (l);
for (int i = 2; i <= mid; i++) { // 枚举题解中的 k.
swa = l / i / i, swb = Min (num, r / i / i);
(swa < swb) and (ans -= (swb - swa - sol (swb) + sol (swa))); // 这边就是真暴力了，只不过这么多括号看着有点晕，仔细看看
num = swa;
}
print (ans);
}