asp网站幻灯片不显示,做外贸有哪些好的网站有哪些内容,搜索引擎优化与推广技术,无锡网站建设制作方案题目传送门#xff1a;
P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言#xff1a;
本题涉及到 欧拉函数#xff0c;素数判断#xff0c;质数#xff0c;筛法 #xff0c;三大知识点#xff0c;相对来说还是比较难的。
本题要求我们计算 …题目传送门
P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言
本题涉及到 欧拉函数素数判断质数筛法 三大知识点相对来说还是比较难的。
本题要求我们计算 也就是对所有满足 和
的整数对 求出它们的最大公约数并将这些最大公约数累加起来。
#使用暴力枚举思路 1、原理 最直接的方法就是通过两层嵌套循环遍历所有可能的 组合对于每一对 计算它们的最大公约数 并将结果累加到总和当中。 代码示例以Python语言示例
sum 0
for i from 1 to n:for j from 1 to n:sum sum gcd(i, j)
print(sum)
##复杂度分析 1、时间复杂度 。因为有两层嵌套循环循环次数为 而计算 通常使用欧几里得算法其时间复杂度为 最坏情况下为O(log n)。 2、空间复杂度: 只使用了常数级的额外空间。
缺点 当 较大时 级别的时间复杂度会导致陈旭运行的时间超出时间的限制。
###枚举最大公约数思路: 原理 我们可以换个角度来想枚举最大公约数 的值然后总计满足 的整数对 的数量 最后将 累加到总和当中。 设 表示 是 的倍数的整数对 的数量。因为 是 的倍数意味着 和 都是 的倍数所以在 1 到 的范围内 有 种选择 也有 种选择那么 。 而我们要求的是 的整数对数量通过容斥从 中减去 是 2d,3d……的整数对数量我们就可以得到 的整数对数量。 代码示例
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、时间复杂度 。虽然比暴力枚举 有一定优化但是仍然比较高因为内层嵌套循环计算 1 的对数时复杂度比较高。 2、空间复杂度 O(1)。
利用莫比乌斯反演优化思路 原理 相信学过数论的人都知道莫比乌斯反演是数论中的重要工具之一它主用于解决这类和最大公约数相关的求和问题。设 表示 的整数对 的数量 表示 是 的倍数整数对 的数量根据定义有 我们根据莫比乌斯反演公式 其中 是莫比乌斯函数。 我们可以先预处理出莫比乌斯函数 然后进行枚举 计算出 再根据莫比乌斯繁衍共识计算 最后将 累加到总和当中。
#####复杂度分析 1、时间复杂度 预处理莫比乌斯函数的时间复杂度为 枚举 d 计算答案的时间复杂度为 。 2、空间复杂度 主要用于存储莫比乌斯函数。
利用欧拉函数优化思路 原理 欧拉函数 表示小于等于 且与 互质的正整数的个数。 我们可以将原问题转化为与欧拉函数相关的形式。对于固定的 我们可以利用欧拉函数的性质来计算满足 的整数对 的数量。
######复杂度分析 1、时间复杂度 预处理欧拉函数的时间复杂度为 枚举 d 计算答案的时间复杂度 所以总的时间复杂度为 。 2、空间复杂度 主要用于存储欧拉函数。
#######代码
#include bits/stdc.h
using namespace std;
typedef long long LL;// 预处理莫比乌斯函数
vectorint num, p;
vectorbool 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;
}
