Crying 与初中数学 - 题解

标签与难度

标签: 数论, 杜教筛, 莫比乌斯反演, 欧拉函数, 整除分块, 积性函数 难度: 2700

题目大意喵~

一位叫 Crying 的同学正在研究如何化简二次根式 $\sqrt{n}$，呐。我们知道，任何正整数 $n$ 都可以唯一地表示成 $n = a^2 \cdot b$ 的形式，其中 $b$ 是一个“无平方因子数”（square-free number），也就是说 $b$ 的任何质因子的幂次都为 1。化简 $\sqrt{n}$ 的过程，就是找到这个最大的 $a$，使得 $\sqrt{n} = a\sqrt{b}$。我们把这对 $(a, b)$ 记为 $(a_n, b_n)$。

题目要求我们计算一个总和：对于从 $1$ 到 $N$ 的所有整数 $n$，分别求出它们的 $(a_n, b_n)$，然后计算 $\sum_{n=1}^N (a_n + b_n)$ 的值。由于 $N$ 可能非常大（比如 $10^{12}$），结果需要对 $2^{64}$ 取模，这正好是 C++ 中 unsigned long long 的自然溢出，非常方便喵~

举个栗子：

• 当 $n=12$ 时，$12 = 2^2 \cdot 3$。所以 $a_{12}=2, b_{12}=3$。
• 当 $n=18$ 时，$18 = 3^2 \cdot 2$。所以 $a_{18}=3, b_{18}=2$。
• 当 $n=7$ 时，$7 = 1^2 \cdot 7$。$7$ 本身就是无平方因子数，所以 $a_7=1, b_7=7$。

我们需要计算的就是 $(a_1+b_1) + (a_2+b_2) + \dots + (a_N+b_N)$。

解题思路分析

这道题是纯纯的数论题，直接从 $1$ 到 $N$ 模拟肯定是不行的说。我们需要运用我的智慧，把这个求和式子变变变，变成一个可以快速计算的形式，喵~

总的求和式可以分成两个独立的部分：

$$S(N) = \sum_{n=1}^{N} (a_n + b_n) = \sum_{n=1}^{N} a_n + \sum_{n=1}^{N} b_n$$

我们分别来推导这两部分的计算方法，呐。

Part 1: 计算 $\sum_{n=1}^{N} a_n$

我们换个角度来思考求和。与其遍历 $n$，不如我们遍历所有可能的 $a_n$ 和 $b_n$ 的值。 根据定义，$n=a_n^2 \cdot b_n$，其中 $b_n$ 是无平方因子数。我们用 $k$ 来表示 $a_n$，用 $m$ 来表示 $b_n$。 那么求和可以写作：

$$\sum_{n=1}^{N} a_n = \sum_{k^2 m \le N, m \text{ is square-free}} k$$

我们可以先枚举 $k$，再统计满足条件的 $m$ 的贡献：

$$\sum_{k=1}^{\sqrt{N}} \sum_{\substack{m=1 \\ m \text{ is square-free}}}^{N/k^2} k$$

令 $Q(x) = \sum_{i=1}^x [i \text{ is square-free}]$，表示 $1$到$x$之间无平方因子数的个数。那么上式就是：

$$\sum_{k=1}^{\sqrt{N}} k \cdot Q(\lfloor N/k^2 \rfloor)$$

根据莫比乌斯反演的一个经典结论，一个数 $i$ 是无平方因子数等价于 $\sum_{d^2|i} \mu(d) = 1$。于是： $Q(x) = \sum_{i=1}^x \sum_{d^2|i} \mu(d) = \sum_{d=1}^{\sqrt{x}} \mu(d) \lfloor x/d^2 \rfloor$。 代入回去：

$$\sum_{k=1}^{\sqrt{N}} k \sum_{d=1}^{\sqrt{N/k^2}} \mu(d) \lfloor \frac{N}{k^2 d^2} \rfloor$$

交换求和次序，令 $j=kd$，我们先枚举 $j$：

$$\sum_{j=1}^{\sqrt{N}} \lfloor \frac{N}{j^2} \rfloor \sum_{k|j} k \cdot \mu(\frac{j}{k})$$

哇！内层的 $\sum_{k|j} k \cdot \mu(\frac{j}{k})$ 是一个狄利克雷卷积的形式，即 $(id * \mu)(j)$，其中 $id(j)=j$。而这个卷积正好等于欧拉函数 $\phi(j)$！ 所以，第一部分的和可以漂亮地化简为：

$$\sum_{n=1}^{N} a_n = \sum_{j=1}^{\sqrt{N}} \phi(j) \lfloor \frac{N}{j^2} \rfloor$$

Part 2: 计算 $\sum_{n=1}^{N} b_n$

同样地，我们对 $\sum b_n$ 进行变形：

$$\sum_{n=1}^{N} b_n = \sum_{k^2 m \le N, m \text{ is square-free}} m = \sum_{k=1}^{\sqrt{N}} \sum_{\substack{m=1 \\ m \text{ is square-free}}}^{N/k^2} m$$

令 $H(x) = \sum_{i=1, i \text{ is square-free}}^x i$，表示 $1$到$x$之间所有无平方因子数之和。上式为：

$$\sum_{k=1}^{\sqrt{N}} H(\lfloor N/k^2 \rfloor)$$

我们同样可以利用莫比乌斯反演来处理 $H(x)$：

$$H(x) = \sum_{i=1}^x i \sum_{d^2|i} \mu(d) = \sum_{d=1}^{\sqrt{x}} \mu(d) \sum_{\substack{i=1 \\ i=t \cdot d^2}}^x i = \sum_{d=1}^{\sqrt{x}} \mu(d) \sum_{t=1}^{\lfloor x/d^2 \rfloor} t \cdot d^2$$

内层的 $\sum_{t=1}^{K} t = \frac{K(K+1)}{2}$，我们记作 $T_K$。于是：

$$H(x) = \sum_{d=1}^{\sqrt{x}} \mu(d) d^2 T_{\lfloor x/d^2 \rfloor}$$

代回到 $\sum b_n$ 的式子中，并利用 $\lfloor \lfloor A \rfloor / B \rfloor = \lfloor A/B \rfloor$：

$$\sum_{n=1}^{N} b_n = \sum_{k=1}^{\sqrt{N}} \sum_{d=1}^{\sqrt{N/k^2}} \mu(d) d^2 T_{\lfloor N/(kd)^2 \rfloor}$$

和刚才一样，交换求和次序，令 $j=kd$：

$$\sum_{j=1}^{\sqrt{N}} T_{\lfloor N/j^2 \rfloor} \sum_{d|j} \mu(d) d^2$$

内层的和 $\sum_{d|j} \mu(d) d^2$ 也是一个积性函数。我们把它记作 $g(j)$。 $g(j)$ 是 $(\mu \cdot sq) * I$ 吗？不对，是 $(\mu \cdot sq) * I$ 在 $j$ 的取值。应该是 $\sum_{d|j} \mu(d)d^2$。 这个函数是积性函数，我们可以看它在质数幂次上的取值：$g(p^k) = \sum_{i=0}^k \mu(p^i)(p^i)^2 = \mu(1)1^2 + \mu(p)p^2 = 1 - p^2$。对于 $i \ge 2$, $\mu(p^i)=0$。所以 $g(p^k) = 1-p^2$ 对所有 $k \ge 1$ 成立。 所以，第二部分的和化简为：

$$\sum_{n=1}^{N} b_n = \sum_{j=1}^{\sqrt{N}} g(j) T_{\lfloor N/j^2 \rfloor} \quad \text{其中 } g(p^k) = 1-p^2$$

合并与计算

现在我们把两部分合在一起：

$$S(N) = \sum_{j=1}^{\sqrt{N}} \left( \phi(j) \lfloor \frac{N}{j^2} \rfloor + g(j) T_{\lfloor N/j^2 \rfloor} \right)$$

这个式子可以通过整除分块（也叫数论分块）来优化。我们发现，对于一段连续的 $j$，$\lfloor N/j^2 \rfloor$ 的值是相同的。 我们可以将 $[1, \sqrt{N}]$ 分成若干个块 $[l, r]$，在每个块内 $\lfloor N/j^2 \rfloor$ 的值都等于 $\lfloor N/l^2 \rfloor$。 对于一个块 $[l, r]$，它的贡献是：

$$\lfloor \frac{N}{l^2} \rfloor \sum_{j=l}^r \phi(j) + T_{\lfloor N/l^2 \rfloor} \sum_{j=l}^r g(j)$$

这就需要我们能快速计算 $\phi$ 和 $g$ 的前缀和，即 $S_\phi(n) = \sum_{i=1}^n \phi(i)$ 和 $S_g(n) = \sum_{i=1}^n g(i)$。

杜教筛登场！

对于比较大的 $n$ (比如 $>\!10^6$)，预处理前缀和是不现实的。这时就要用杜教筛了喵！杜教筛是一种在亚线性时间内计算积性函数前缀和的强大算法。

1. 求 $S_\phi(n)$: 我们知道一个经典的狄利克雷卷积恒等式：$\phi * I = id$，即 $\sum_{d|n} \phi(d) = n$。 利用这个性质，可以推导出 $S_\phi(n)$ 的递推式：

   $$S_\phi(n) = \sum_{i=1}^n i - \sum_{k=2}^n S_\phi(\lfloor n/k \rfloor) = \frac{n(n+1)}{2} - \sum_{k=2}^n S_\phi(\lfloor n/k \rfloor)$$

2. 求 $S_g(n)$: 对于 $g(j)=\sum_{d|j}\mu(d)d^2$，我们需要找到一个简单的函数 $h$ 使得 $g*h$ 的前缀和容易计算。 经过一番探索（推导过程有点小复杂呢喵~），我们发现 $g$ 和函数 $sq(n)=n^2$ 的狄利克雷卷积是单位函数 $I(n)=1$。即 $(g * sq)(n) = 1$。 证明：$(g*sq)(p^k) = \sum_{i=0}^k g(p^i)(p^{k-i})^2 = 1 \cdot p^{2k} + \sum_{i=1}^k (1-p^2)p^{2(k-i)} = p^{2k} + (1-p^2) \frac{p^{2k}-1}{p^2-1} = p^{2k} - (p^{2k}-1) = 1$。 所以，$(g*sq)(n)=1$ 对所有 $n$ 成立。 利用这个性质，可以推导出 $S_g(n)$ 的递推式：

   $$S_g(n) = \sum_{i=1}^n 1 - \sum_{k=2}^n k^2 S_g(\lfloor n/k \rfloor) = n - \sum_{k=2}^n k^2 S_g(\lfloor n/k \rfloor)$$

这两个递推式都可以用整除分块和记忆化搜索来高效实现。我们先用线性筛预处理出一部分小范围（比如到 $5 \cdot 10^6$）的前缀和，对于更大的值就用杜教筛递归计算。

最终，我们的算法流程是：

1. 线性筛预处理小范围内的 $\phi(n)$ 和 $g(n)$ 以及它们的前缀和。
2. 实现两个杜教筛函数，分别计算 $S_\phi(n)$ 和 $S_g(n)$。
3. 使用整除分块，遍历 $[1, \sqrt{N}]$ 的所有块 $[l, r]$。
4. 在每个块内，计算出块对应的常数值 $d = \lfloor N/l^2 \rfloor$ 和 $T_d$。
5. 调用杜教筛函数得到 $S_\phi(r), S_\phi(l-1), S_g(r), S_g(l-1)$，从而计算出 $\sum_{j=l}^r \phi(j)$ 和 $\sum_{j=l}^r g(j)$。
6. 累加每个块的贡献，得到最终答案，喵~

代码实现

这是我仔细分析和重构后的代码，希望能帮助你理解整个过程哦！

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>

// 使用 unsigned long long 来处理对 2^64 的取模
using ull = unsigned long long;
// 使用 __int128 来防止中间计算溢出，特别是平方和、立方和
using int128 = __int128;

// 预处理数组的最大值，N_max^(2/3) 是一个比较理想的取值，这里取 5*10^6
const int PRECOMPUTE_LIMIT = 5000000;

// N 是题目输入的最大值
ull N;

// 预处理数组
std::vector<int> primes;
bool is_prime[PRECOMPUTE_LIMIT + 1];
ull phi[PRECOMPUTE_LIMIT + 1];
ull g[PRECOMPUTE_LIMIT + 1]; // g(j) = sum_{d|j} mu(d)d^2
ull sum_phi[PRECOMPUTE_LIMIT + 1];
ull sum_g[PRECOMPUTE_LIMIT + 1];

// 杜教筛记忆化
std::unordered_map<ull, ull> memo_sum_phi;
std::unordered_map<ull, ull> memo_sum_g;

// 线性筛预处理 phi 和 g
void sieve(int limit) {
    std::fill(is_prime, is_prime + limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    phi[1] = 1;
    g[1] = 1;

    for (int i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
            g[i] = 1 - (ull)i * i; // g(p) = 1 - p^2
        }
        for (int p : primes) {
            if ((long long)i * p > limit) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                g[i * p] = g[i]; // g(p^k) = g(p) if i contains p
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
                g[i * p] = g[i] * g[p]; // g is multiplicative
            }
        }
    }

    // 计算前缀和
    sum_phi[0] = sum_g[0] = 0;
    for (int i = 1; i <= limit; ++i) {
        sum_phi[i] = sum_phi[i - 1] + phi[i];
        sum_g[i] = sum_g[i - 1] + g[i];
    }
}

// 计算 1^2 + 2^2 + ... + n^2
ull sum_sq(ull n) {
    int128 N128 = n;
    int128 res = N128 * (N128 + 1) * (2 * N128 + 1) / 6;
    return (ull)res;
}

// 杜教筛计算 phi 的前缀和
ull get_sum_phi(ull n) {
    if (n <= PRECOMPUTE_LIMIT) {
        return sum_phi[n];
    }
    if (memo_sum_phi.count(n)) {
        return memo_sum_phi[n];
    }

    // S_phi(n) = n(n+1)/2 - sum_{k=2 to n} S_phi(n/k)
    int128 n128 = n;
    ull res = (ull)(n128 * (n128 + 1) / 2);
    
    for (ull l = 2, r; l <= n; l = r + 1) {
        ull val = n / l;
        r = n / val;
        res -= (r - l + 1) * get_sum_phi(val);
    }
    return memo_sum_phi[n] = res;
}

// 杜教筛计算 g 的前缀和
ull get_sum_g(ull n) {
    if (n <= PRECOMPUTE_LIMIT) {
        return sum_g[n];
    }
    if (memo_sum_g.count(n)) {
        return memo_sum_g[n];
    }
    
    // S_g(n) = n - sum_{k=2 to n} k^2 * S_g(n/k)
    ull res = n;

    for (ull l = 2, r; l <= n; l = r + 1) {
        ull val = n / l;
        r = n / val;
        // sum_{k=l to r} k^2 = sum_sq(r) - sum_sq(l-1)
        res -= (sum_sq(r) - sum_sq(l - 1)) * get_sum_g(val);
    }
    return memo_sum_g[n] = res;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    sieve(PRECOMPUTE_LIMIT);
    
    std::cin >> N;

    ull total_sum_a = 0;
    ull total_sum_b = 0;
    ull sqrt_N = sqrt(N);

    // 整除分块计算 S(N)
    for (ull l = 1, r; l <= sqrt_N; l = r + 1) {
        ull d = N / (l * l);
        // 为了安全起见，用 sqrt(double) 计算 r
        // double d_double = d;
        // r = sqrt( (double)N / d_double );
        // 或者直接用整数，因为 d = N/(l*l) <= N/l^2
        r = sqrt(N / d);

        // 计算 sum a_n 部分
        total_sum_a += d * (get_sum_phi(r) - get_sum_phi(l - 1));

        // 计算 sum b_n 部分
        // T_d = d(d+1)/2
        int128 d128 = d;
        ull T_d = (ull)(d128 * (d128 + 1) / 2);
        total_sum_b += T_d * (get_sum_g(r) - get_sum_g(l - 1));
    }
    
    std::cout << total_sum_a + total_sum_b << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(M + N^{1/3})$ 或 $O(M + (\sqrt{N})^{2/3})$。

  • 线性筛：预处理部分复杂度是 $O(M)$，其中 $M$ 是 PRECOMPUTE_LIMIT。
  • 杜教筛：若预处理到 $M=N^{2/3}$，杜教筛的复杂度是 $O(N^{2/3})$。在这里，我们需要的最大前缀和是到 $\sqrt{N}$。若预处理到 $M = (\sqrt{N})^{2/3} = N^{1/3}$，则计算所有需要的前缀和总复杂度为 $O(N^{1/3})$。我们的 $M=5 \cdot 10^6$ 比 $N^{1/3}$（当 $N=10^{12}$ 时为 $10^4$）大得多，所以杜教筛部分会非常快。
  • 主循环: 整除分块的循环次数大约是 $O(\sqrt{\sqrt{N}}) = O(N^{1/4})$ 次。每次循环内部调用杜教筛函数。由于有记忆化，每个需要的值只会被计算一次。
  • 综上，总复杂度由预处理和杜教筛主导，大致可以认为是 $O(M + (\sqrt{N})^{2/3})$。对于 $N=10^{12}, M=5 \cdot 10^6$，复杂度是 $O(5 \cdot 10^6 + (10^6)^{2/3}) = O(5 \cdot 10^6 + 10^4)$，完全可以在时限内完成。

• 空间复杂度: $O(M + N^{1/4})$

  • 预处理数组占用了 $O(M)$ 的空间。
  • 杜教筛的记忆化 unordered_map 会存储大约 $O((\sqrt{N})^{1/2}) = O(N^{1/4})$ 个状态，所以空间复杂度是 $O(M+N^{1/4})$。

知识点总结

1. 问题转化: 将复杂的求和问题通过改变求和对象（从 $n$ 到 $a_n, b_n$ 的组合）进行简化，是数论题中的常用技巧。
2. 积性函数: 欧拉函数 $\phi(n)$ 和我们构造的 $g(n)$ 都是积性函数，这使得我们可以利用线性筛来预处理它们的值。
3. 狄利克雷卷积: 这是解决数论问题的有力武器！本题中用到了 $\phi * I = id$ 和 $((\mu \cdot sq)*I)*sq = I$ （即 $g*sq=I$）两个关键恒等式。
4. 莫比乌斯反演: 它是推导 $Q(x)$ 和 $H(x)$ 公式的核心，帮助我们将 "square-free" 这个条件转化为了与 $\mu$ 函数相关的求和。
5. 整除分块 (数论分块): 对于形如 $\sum_{i=1}^n f(i) \lfloor n/i \rfloor$ 的和式，通过将 $\lfloor n/i \rfloor$ 值相同的 $i$ 分成一块来计算，可以大大降低时间复杂度。本题中我们用到了它的变体 $\sum_{j=1}^{\sqrt{N}} F(j, \lfloor N/j^2 \rfloor)$。
6. 杜教筛: 当需要计算积性函数在远超预处理范围的前缀和时，杜教筛是标准的高效算法。它的核心思想是利用一个巧妙的递推关系，结合记忆化搜索和整除分块来加速计算。

希望这篇题解能帮你彻底搞懂这道有趣的数论题，喵~ 如果有任何疑问，随时可以再来问我哦！