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

网站建设如何选择良好的服务器/网站广告制作

网站建设如何选择良好的服务器,网站广告制作,酒泉网站建设,齐家网装修公司地址题目传送门: P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前言: 本题涉及到 欧拉函数,素数判断,质数,筛法 ,三大知识点,相对来说还是比较难的。 本题要求我们计算 …

题目传送门:

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.fp688.cn/news/561.html

相关文章:

  • 新网站怎么做/云浮seo
  • 公司网站建设备选方案评价标准/广州网页推广公司
  • 广州门户网站/成人营销管理培训班
  • 帝国手机网站怎么做/电话营销销售系统
  • 平凉市住房和城乡建设厅网站/软件开发app制作
  • 弱电工程公司网站怎么做/seo关键词布局
  • 如何用jsp做简单的网站/百度有钱花人工客服
  • 市民服务中心网站建设/百度推广方法
  • 创建一个网站的英文/域名注册服务商
  • 龙岩纪检委网站/营销策划案ppt优秀案例
  • 静态学校网站做毕业设计/seo云优化平台
  • 唐山做网站建设的公司/东莞网站推广运营公司
  • 域名网站/正规网络推广服务
  • 沂源县建设局网站/关键词优化收费标准
  • 从什么网站找做游戏的代码/结构优化设计
  • 网站排名方案/电商广告网络推广
  • 深圳做购物网站/seo网站优化培训班
  • 网站建设和优化的好处/免费网站seo优化
  • 网站建设小江/营销号
  • 阜宁做网站哪家公司好/网站怎么做优化排名
  • 金华职院优质校建设网站/国外免费发产品的b2b平台
  • 网站关键词部署/seo外包网站
  • 北京西直门附近网站建设公司/怎么制作网页教程
  • php做的卖水果网站/四川seo关键词工具
  • 青岛做企业网站的公司/2022年app拉新推广项目
  • 网站建设窗口框架/百度首页网站推广多少钱一年
  • 什么网站可以做相册视频/什么关键词可以搜到那种
  • 宣威网站建设/cilimao磁力猫最新版地址
  • 旅游网站建设毕业设计/关键词爱站网
  • 160外发加工网/seo综合查询工具可以查看哪些数据