当前位置：首页 > news >正文

洛谷题目： P2398 GCD SUM 题解（本题较难，省选-难度）

news 2025/8/30 15:23:17

题目传送门：

P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言：

本题涉及到欧拉函数，素数判断，质数，筛法，三大知识点，相对来说还是~~比较难的。~~

本题要求我们计算 $\sum_{i = 1}^{n}\sum_{j = 1}^{n}\gcd(i, j)$ ，也就是对所有满足 $1\leq i\leq n$ 和 $1\leq j \leq n$

的整数对 $(i,j)$ ，求出它们的最大公约数并将这些最大公约数累加起来。

#使用暴力枚举思路：

1、原理：

最直接的方法就是通过两层嵌套循环遍历所有可能的 $(i,j)$ 组合，对于每一对 $(i,j)$ 计算它们的最大公约数 $gcd(i,j)$ ，并将结果累加到总和当中。

代码示例（以Python语言示例）：

sum = 0
for i from 1 to n:for j from 1 to n:sum = sum + gcd(i, j)
print(sum)

##复杂度分析：

1、时间复杂度：

$O(n^{2} logn)$ 。因为有两层嵌套循环，循环次数为 $n *n=n^{2}$ ，而计算 $gcd(i,j)$ 通常使用欧几里得算法，其时间复杂度为 $O(log \: min(i,j))$ ，最坏情况下为O(log n)。

2、空间复杂度:

$O(1)$ ，只使用了常数级的额外空间。

缺点： $(i,j)$

当 $n$ 较大时， $n^{2}$ 级别的时间复杂度会导致陈旭运行的时间超出时间的限制。

###枚举最大公约数思路:

原理：

我们可以换个角度来想，枚举最大公约数 $d$ 的值，然后总计满足 $gcd(i,j)=b$ 的整数对 $(i,j)$ 的数量 $cnt_{d}$ ，最后将 $d*cnt_{d}$ 累加到总和当中。

设 $g(d)$ 表示 $gcd(i,j)$ 是 $d$ 的倍数的整数对 $(i,j)$ 的数量。因为 $gcd(i,j)$ 是 $d$ 的倍数意味着 $i$ 和 $j$ 都是 $d$ 的倍数，所以在 1 到 $n$ 的范围内 $i$ 有 $\lfloor \frac{n}{d}\rfloor$ 种选择， $j$ 也有 $\lfloor \frac{n}{d}\rfloor$ 种选择，那么 $g(d)= \frac{n}{d} * \frac{n}{d}$ 。

而我们要求的是 $gcd(i,j)=d$ 的整数对数量，通过容斥，从 $g(d)$ 中减去 $gcd(i,j)$ 是 2d,3d，……的整数对数量，我们就可以得到 $gcd(i,j)=d$ 的整数对数量。

代码示例：

sum = 0
for d from 1 to n:cnt = 0for i from 1 to n/d:for j from 1 to n/d:if gcd(i, j) == 1:cnt = cnt + 1sum = sum + d * cnt
print(sum)

####复杂度分析：

1、时间复杂度：

$O(n^{2} logn)$ 。虽然比暴力枚举有一定优化，但是仍然比较高，因为内层嵌套循环计算 $gcd(i,j)$ =1 的对数时复杂度比较高。

2、空间复杂度：

O(1)。

利用莫比乌斯反演优化思路：

原理：

相信学过数论的人都知道，莫比乌斯反演是数论中的重要工具之一，它主用于解决这类和最大公约数相关的求和问题。设 $f(d)$ 表示 $gcd(i,j)$ 的整数对 $(i,j)$ 的数量， $g(d)$ 表示 $gcd(i,j)$ 是 $d$ 的倍数整数对 $(i,j)$ 的数量，根据定义有

我们根据莫比乌斯反演公式，，其中是莫比乌斯函数。

我们可以先预处理出莫比乌斯函数，然后进行枚举 $d$ ，计算出 $g(d)=\left\lfloor\frac{n}{d}\right\rfloor\times\left\lfloor\frac{n}{d}\right\rfloor$ ，再根据莫比乌斯繁衍共识计算 $f(d)$ ，最后将 $d*f(d)$ 累加到总和当中。

#####复杂度分析：

1、时间复杂度：

预处理莫比乌斯函数的时间复杂度为 $O(n)$ ，枚举 d 计算答案的时间复杂度为 $O(nlogn)$ 。

2、空间复杂度：

$O(n)$ ，主要用于存储莫比乌斯函数。

利用欧拉函数优化思路：

原理：

欧拉函数表示小于等于 $n$ 且与 $n$ 互质的正整数的个数。

我们可以将原问题转化为与欧拉函数相关的形式。对于固定的 $d$ ，我们可以利用欧拉函数的性质来计算满足 $gcd(i,j)=d$ 的整数对 $(i,j)$ 的数量。

######复杂度分析：

1、时间复杂度：

预处理欧拉函数的时间复杂度为 $O(nloglogn)$ ，枚举 d 计算答案的时间复杂度 $O(n)$ ，所以总的时间复杂度为 $O(nloglogn)$ 。

2、空间复杂度：

$O(n)$ ，主要用于存储欧拉函数。

#######代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;// 预处理莫比乌斯函数
vector<int> num, p;
vector<bool> s;
void M(int n) {num.resize(n + 1);s.resize(n + 1, true);num[1] = 1;for (int i = 2; i <= n; ++i) {if (s[i]) {p.push_back(i);num[i] = -1;}for (int j = 0; j < p.size() && i * p[j] <= n; ++j) {s[i * p[j]] = false;if (i % p[j] == 0) {num[i * p[j]] = 0;break;}num[i * p[j]] = -num[i];}}
}int main() {int n;cin >> n;M(n);LL ans = 0;// 枚举 gcd 的值 dfor (int d = 1; d <= n; ++d) {LL g = 0;int m = n / d;// 计算 g(d)for (int k = 1; k <= m; ++k) {g += (LL)num[k] * (m / k) * (m / k);}ans += d * g;}cout << ans << endl;return 0;
}

查看全文

http://www.lryc.cn/news/536035.html