题解 SP4168 【SQFREE - Square-free integers】

Sooke · 2018-12-05 11:38:28 · 题解

解题思路

有平方数因数，等同于有两个相同的质因子，由此联想到一个常见的函数——莫比乌斯函数。

先来看它的定义：

注意到，仅当 x 的质因子互不相同，\mu(x) \neq 0，否则 \mu(x) = 0。

更一般地，我们可以把该函数取个平方，令 \mu^2(x)=\mu(x)^2。此时 x 的质因数互不相同，有 \mu^2(x)=1，否则 \mu^2(x) = 0。

这样，答案就可以直接表示为 \sum\limits_{i=1}^{n}1-\mu^2(i)。\mu^2(x) 是积性函数，可以 O(n) 线筛，算法整体复杂度也是 O(n) 的，不足以通过此题。

于是我们换个角度，考虑在 [1,\ n] 中，有多少个数是 x 代表的平方数（即 x^2） 的倍数。

显然是 \lfloor \frac{n}{x^2} \rfloor 个，对吧？那 n - \sum\limits_{i=1}^{n}\lfloor \frac{n}{i^2} \rfloor 就是答案了吗？当然不是，有大量的数被重复计算了。

例如 36，它等于 2^2 \times 3^2，在枚举 2 和 3 的时候它就会被重复计算。

怎么办呢？加加减减弄对呗！

可以发现，当一个数分别是两个质数代表的平方数的倍数，它肯定也是那两个质数的积，代表的平方数的倍数，所以我们可以利用这个“积”来去掉重复计算的部分。我们设 f(x) 表示 x 的质因子数量（x 没有平方数因数），如果当 f(x) = 0 时，x 只能为 1，这个时候我们加，就是全部的 n 个数。如果 f(x) = 1，这个时候我们减，f(x) = 2，再加……以此类推。

但上面的讨论漏掉了有平方数因数的贡献，这样弄出来对吗？

经过计算，这样是对的！我们宁可让有平方数因数的数没有贡献！

综上所述，我们只让质因子互不相同的数有贡献，贡献的正负取决于其质因子数量的奇偶性。

等等，这不就是 \mu(x) 的定义吗！不知不觉它又回来了！整理一下，答案等于 \sum\limits_{i=1}^{n}\lfloor \frac{n}{i^2} \rfloor \mu(i)，好神奇啊。

但这个式子还是 O(n) 的呢……事实上，i > \sqrt{n} 时，\lfloor \frac{n}{i^2} \rfloor 恒等于 0，我们只需要枚举到 \sqrt{n}。

再考虑优化，\lfloor \frac{n}{i^2} \rfloor 是整除分块的基本形式，我们用整除分块优化，给 \mu(x) 搞个前缀和。

最终时间复杂度是 O(\sqrt{n} + T\sqrt{\sqrt{n}}) 的，很快。莫比乌斯函数怎么线筛就不用说了吧。

代码实现

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>

const int maxT = 105, maxSqrt = 10000005;

int t, m, sqrtN, pri[maxSqrt / 10], mu[maxSqrt], sum[maxSqrt];
long long n, ans, q[maxT];
bool vis[maxSqrt];

void init() {
    mu[1] = sum[1] = 1;
    for (int i = 2; i <= sqrtN; i++) {
        if (!vis[i]) { pri[++m] = i; mu[i] = -1; }
        for (int j = 1; j <= m; j++) {
            int k = i * pri[j];
            if (k > sqrtN) { break; } vis[k] = true;
            if (i % pri[j] == 0) { break; } mu[k] = -mu[i];
        }
        sum[i] = sum[i - 1] + mu[i];
    }
}

int main() {
    scanf("%d", &t);
    for (int i = 1; i <= t; i++) { scanf("%lld", &q[i]); n = std::max(n, q[i]); }
    sqrtN = sqrt(n); init(); // 线性求莫比乌斯函数, 前缀和.
    for (int i = 1; i <= t; i++) {
        n = q[i]; ans = 0;
        for (long long l = 1, r; l <= n; l = r + 1) {
            if (n / (l * l) == 0) { break; }
            r = sqrt(n / (n / (l * l))); ans += n / (l * l) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}