E. Madoka and The Best University - 题解

比赛与标签

比赛: Codeforces Round 818 (Div. 2) 标签: math, number theory 难度: *2200

题目大意喵~

Mado-chan 在入学考试中遇到了一个难题，需要我们帮忙的说！(ฅ'ω'ฅ)

题目是这样的：给定一个正整数 n，我们需要找到所有满足 a + b + c = n 的正整数三元组 (a, b, c)，然后计算所有这些三元组的 lcm(c, gcd(a, b)) 的总和。因为答案可能会很大，所以需要对 10^9 + 7 取模。

简单来说，就是要计算这个式子：

$$\sum_{a,b,c \ge 1, a+b+c=n} \operatorname{lcm}(c, \gcd(a, b)) \pmod{10^9 + 7}$$

比如当 n=3 时，只有一种三元组 (1, 1, 1)，所以答案就是 lcm(1, gcd(1, 1)) = 1。 当 n=5 时，有很多组合，比如 (1, 1, 3), (1, 2, 2), (2, 1, 2) 等等，把它们对应的 lcm 值加起来就是答案啦！

解题思路的奇妙旅程喵~

直接暴力枚举 a, b, c 肯定会超时的说，复杂度是 O(n^2)，对于 n 高达 10^5 的数据是绝对不行的呐。所以，我们必须施展一些数学魔法来优化它！

第一步：改变求和顺序

这个求和式有三个变量 a, b, c，它们被 a+b+c=n 束缚在一起，非常不自由喵。我们来尝试换一个角度看问题。式子里有一个 gcd(a, b)，这是一个非常好的突破口！

我们不枚举 a, b, c，而是去枚举 g = gcd(a, b) 的值。

那么原式就可以改写成：

$$\sum_{g=1}^{n} \sum_{a,b,c \ge 1, a+b+c=n, \gcd(a,b)=g} \operatorname{lcm}(c, g)$$

第二步：化简内部求和

现在我们来处理内部的求和。对于一个固定的 g，我们需要找到满足 a+b+c=n 且 gcd(a,b)=g 的 (a,b,c)。

设 a = g \cdot a'，b = g \cdot b'，那么 gcd(a', b') = 1。 代入 a+b+c=n，得到 g(a' + b') + c = n。

因为 a, b, c 都是正整数，所以 a' \ge 1, b' \ge 1, c \ge 1。 这意味着 a+b = g(a'+b') \ge 2g，所以 c = n - (a+b) \le n - 2g。 同时 c \ge 1，所以 g 的取值范围是 1 \le g \le (n-1)/2。

现在，我们把求和变量从 (a,b,c) 换成 (g, c) 和 (a', b')。 对于固定的 g 和 c，我们需要计算有多少对 (a', b') 满足 a' + b' = (n-c)/g 且 gcd(a', b')=1。

这是一个经典的问题！满足 x+y=S 且 gcd(x,y)=1 的正整数对 (x,y) 的数量是 φ(S)，也就是欧拉函数。 所以，对于固定的 g 和 c，只要 g 能整除 n-c，贡献就是 lcm(c, g) \times φ((n-c)/g)。

于是，我们的式子变成了：

$$\sum_{g=1}^{(n-1)/2} \sum_{c=1, g|(n-c)}^{n-2g} \operatorname{lcm}(c, g) \cdot \varphi\left(\frac{n-c}{g}\right)$$

这个式子看起来还是很复杂，喵... 我们需要进一步的变换！

第三步：再次换元，最终推导！

我们发现 (n-c)/g 这种形式很适合换元。 令 k = (n-c)/g，那么 c = n - k \cdot g。

我们来看看 k 的取值范围：

• 因为 c \ge 1，所以 n - kg \ge 1 \implies kg \le n-1 \implies k \le (n-1)/g。
• 因为 c \le n-2g，所以 n - kg \le n-2g \implies kg \ge 2g \implies k \ge 2。

所以，k 的取值范围是 2 \le k \le (n-1)/g。

现在，我们的求和变量变成了 g 和 k，式子也变得清晰多了：

$$\sum_{g=1}^{(n-1)/2} \sum_{k=2}^{(n-1)/g} \operatorname{lcm}(n - k \cdot g, g) \cdot \varphi(k)$$

接下来是整个推导中最最关键的一步！处理 lcm(n - kg, g)。 根据 lcm(x, y) = (x \cdot y) / gcd(x, y)，我们有：

$$\operatorname{lcm}(n - k \cdot g, g) = \frac{(n - k \cdot g) \cdot g}{\gcd(n - k \cdot g, g)}$$

根据欧几里得算法的性质，我们知道 gcd(A - B, B) = gcd(A, B)。所以：

$$\gcd(n - k \cdot g, g) = \gcd(n, g)$$

哇！这个化简太漂亮了喵！(>ω<)

代入回去，lcm 项就变成了：

$$\operatorname{lcm}(n - k \cdot g, g) = \frac{(n - k \cdot g) \cdot g}{\gcd(n, g)}$$

我们的总和式子就变成了：

$$\sum_{g=1}^{(n-1)/2} \sum_{k=2}^{(n-1)/g} \frac{(n - k \cdot g) \cdot g}{\gcd(n, g)} \cdot \varphi(k)$$

把和 k 无关的项提到外面去：

$$\sum_{g=1}^{(n-1)/2} \frac{g}{\gcd(n, g)} \left( \sum_{k=2}^{(n-1)/g} (n - k \cdot g) \cdot \varphi(k) \right)$$

第四步：预处理与前缀和

现在我们聚焦于内部的这个和式，令 m = (n-1)/g：

$$\sum_{k=2}^{m} (n - k \cdot g) \cdot \varphi(k) = \sum_{k=2}^{m} n \cdot \varphi(k) - \sum_{k=2}^{m} k \cdot g \cdot \varphi(k)$$

$$= n \left( \sum_{k=2}^{m} \varphi(k) \right) - g \left( \sum_{k=2}^{m} k \cdot \varphi(k) \right)$$

这两个和式 ∑φ(k) 和 ∑kφ(k) 可以通过预处理和前缀和来快速计算！

我们先用 O(N log log N) 的线性筛法预处理出所有 φ(i)。 然后定义两个前缀和数组：

• T[m] = ∑_{i=1}^{m} φ(i)
• U[m] = ∑_{i=1}^{m} i \cdot φ(i)

那么，∑_{k=2}^{m} φ(k) = T[m] - φ(1) = T[m] - 1。 同理，∑_{k=2}^{m} k \cdot φ(k) = U[m] - 1 \cdot φ(1) = U[m] - 1。

所以，内部和式可以 O(1) 计算出来：

$$n \cdot (T[m] - 1) - g \cdot (U[m] - 1)$$

这不就和代码里的 term1 - term2 完全对应上了嘛！

最终，我们的总和就是：

$$\text{ans} = \sum_{g=1}^{(n-1)/2} \frac{g}{\gcd(n, g)} \left( n \cdot (T[\lfloor\frac{n-1}{g}\rfloor] - 1) - g \cdot (U[\lfloor\frac{n-1}{g}\rfloor] - 1) \right)$$

这个式子我们就可以在 O(N log N) 的时间内算出来啦！

代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义常量，最大n和模数
const int max_n = 100000;
const long long mod = 1000000007;

// 一个小小的gcd函数
long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    // 预处理欧拉函数 phi[i]
    vector<long long> phi(max_n + 1);
    for (int i = 1; i <= max_n; i++) {
        phi[i] = i;
    }
    // 使用类似筛法的方式计算 phi
    for (int i = 2; i <= max_n; i++) {
        if (phi[i] == i) { // i 是一个质数
            for (int j = i; j <= max_n; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }

    // 预处理两个前缀和数组 T 和 U
    // T[i] = sum(phi[k] for k=1 to i)
    // U[i] = sum(k * phi[k] for k=1 to i)
    vector<long long> T(max_n + 1, 0);
    vector<long long> U(max_n + 1, 0);
    for (int i = 1; i <= max_n; i++) {
        T[i] = (T[i - 1] + phi[i]) % mod;
        U[i] = (U[i - 1] + (long long)i * phi[i]) % mod;
    }

    long long n_val;
    cin >> n_val;

    // 题目保证 n >= 3，但还是做一个小检查
    if (n_val < 3) {
        cout << 0 << endl;
        return 0;
    }

    long long ans = 0;
    // 开始主循环，枚举 g (也就是我们推导中的 d)
    // 循环到 n-1 是可以的，因为当 m < 2 时会自动跳过
    for (long long g = 1; g <= n_val - 1; g++) {
        // m = floor((n-1)/g)，对应推导中的 k 的上界
        long long m = (n_val - 1) / g;
        // k 的下界是 2，所以 m 必须至少是 2
        if (m < 2) continue;
        
        // 计算 g / gcd(n, g)
        long long d_gcd = gcd(n_val, g);
        long long k_factor = g / d_gcd;

        // 计算内部的和式: n * (T[m]-1) - g * (U[m]-1)
        // 注意 T[m]-1 和 U[m]-1 可能会是负数，要小心处理取模
        long long term1 = (n_val % mod) * ((T[m] - 1 + mod) % mod) % mod;
        long long term2 = (g % mod) * ((U[m] - 1 + mod) % mod) % mod;
        long long X = (term1 - term2 + mod) % mod;

        // 将当前 g 的贡献累加到答案中
        long long add = (k_factor % mod) * X % mod;
        ans = (ans + add) % mod;
    }
    
    // 最终结果也要确保是正数
    ans = (ans + mod) % mod;
    cout << ans << endl;
    
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log log N + N log N) 的说。

  • 预处理 phi 函数使用的是线性筛的变体，时间复杂度为 O(N log log N)。
  • 预处理前缀和数组 T 和 U 的时间复杂度是 O(N)。
  • 主循环从 g=1 到 n-1，每次循环内部需要计算一次 gcd(n, g)，其复杂度为 O(log n)。所以主循环的复杂度是 O(N log N)。
  • 综上，总的时间复杂度由主循环主导，为 O(N log N)。

• 空间复杂度: O(N) 的说。

  • 我们需要 phi, T, U 三个数组来存储预处理的结果，每个数组的大小都是 N+1，所以空间复杂度是 O(N)。

知识点与总结喵~

这道题是一道非常精彩的数论题，完美地将欧拉函数、GCD性质和前缀和优化结合在了一起，真是让人心跳加速呢！(〃'▽'〃)

1. 核心思想: 和式变换与换元。面对复杂的多变量求和，不要害怕，尝试固定一部分变量，或者用新的变量来替换复杂的表达式，往往能找到化简的道路。
2. 关键性质: gcd(A - k*B, B) = gcd(A, B)。这是欧几里得算法的直接推论，也是本题能够成功化简的核心。记下这个小技巧，以后会很有用的说！
3. 重要工具: 欧拉函数 φ(n)。它在计数问题中，特别是与 gcd 相关的计数中，扮演着不可或缺的角色。φ(n) 表示小于等于 n 且与 n 互质的正整数的个数。
4. 编程技巧: 预处理与前缀和。对于那些在循环中会被反复计算，并且形式规整的求和，一定要想到用前缀和来优化！这能将求一个区间的和从 O(L) 降到 O(1)，是算法竞赛中必备的技能喵。
5. 注意事项: 在进行模运算时，尤其是减法，一定要记得 (a - b % mod + mod) % mod 的写法，防止出现负数导致结果错误哦！

希望这篇题解能帮助你理解这道有趣的题目！继续加油，享受算法的乐趣吧，喵~！