【题解】P2568 GCD

矫情吗；* 2022-01-12 03:09 179阅读 0赞

\\(Description:\\)

> 求x,y小于n中gcd(x,y)为质数的对数

\\(Sample\\) \\(Input:\\)

> 4

\\(Sample\\) \\(Output:\\)

> 4

\\(Hint:\\)

> x,y互换算不同
> 
> n<=1e7

这题，我一看…………

好一题欧拉函数。

啊，什么啊 ？ 欧拉函数？

没错，我们化化式子。

$\\sum\_\{p\}^\{Prime\}\\sum\_\{i=1\}^\{p\}\\sum\_\{j=1\}^\{p\} $ $ 1(gcd(i,j)=p)/0(gcd(i,j!=p))$

gcd化简：

\\(\\sum\_\{p\}^\{Prime\}\\sum\_\{i=1\}^\{n/p\}\\sum\_\{j=1\}^\{n/p\}gcd(i,j)=1\\)

欧拉函数化简：

\\(\\sum\_\{p\}^\{Prime\}\\sum\_\{i=1\}^\{n/p\}2\*\\phi(i)-1\\)

那么在对\\(\\phi(i)\\)前缀和优化一下就可以了。

顺便提一提：这题别开太多没用的东西，别随手longlong

#include<bits/stdc++.h> using namespace std; typedef long long LL; int n,cnt; LL ans; const int N=1e7; bool v[N+5]; int main(){ scanf("%d",&n); int *p,*phi; p=new int [n+5]; phi=new int [n+5]; LL *s; s=new LL [n+5]; memset(p,0,sizeof(p)); memset(phi,0,sizeof(phi)); memset(s,0,sizeof(s)); v[1]=1;phi[1]=1; for(int i=2;i<=n;++i){ if(!v[i]) p[++cnt]=i,phi[i]=i-1; for(int j=1;j<=cnt && i*p[j]<=n;++j){ v[i*p[j]]=1; if(i%p[j]!=0) phi[i*p[j]]=phi[i]*phi[p[j]]; else { phi[i*p[j]]=phi[i]*p[j];break;} } } for(int i=1;i<=n;++i) s[i]=(LL)(s[i-1]+phi[i]); for(int i=1;i<=cnt;++i) ans+=s[n/p[i]]*2-1; delete [] p; delete [] phi; delete [] s; printf("%lld\n",ans); return 0; }

转载于:https://www.cnblogs.com/JCNL666/p/10680277.html

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关【欧拉函数】 P2568 GCD P2398 GCD SUM

[P2568 GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2568 GCD - _ _ _ _luogu.com.cn] 题意： ![dc

太过爱你忘了你带给我的痛/ 2024年03月29日 14:35/ 0 赞/ 11 阅读

相关【题解】P2568 GCD

\\(Description:\\) > 求x,y小于n中gcd(x,y)为质数的对数 \\(Sample\\) \\(Input:\\) > 4 \\(Sample\

矫情吗；*/ 2022年01月12日 03:09/ 0 赞/ 180 阅读

相关洛谷P2257 YY的GCD

莫比乌斯反演还是把gcd换成莫比乌斯函数，在最外层枚举素数p，对于每个素数p，gcd莫比乌斯反演 include <bits/stdc++.h> de

Dear 丶/ 2022年01月07日 05:21/ 0 赞/ 125 阅读

相关 P2568 GCD

[传送门][Link 1] 设 $f\[x\]=\\sum\_i^N\\sum\_j^N\[gcd(i,j)==x\]$ 那么答案就是 $Ans=\\sum\_\{prim

骑猪看日落/ 2021年12月10日 02:53/ 0 赞/ 177 阅读

相关洛谷P2257 YY的GCD

莫比乌斯反演还是把gcd换成莫比乌斯函数，在最外层枚举素数p，对于每个素数p，gcd莫比乌斯反演 include <bits/stdc++.h> de

忘是亡心i/ 2021年11月08日 17:26/ 0 赞/ 174 阅读

相关题解洛谷P2568 GCD

\\(update\\ \\ \\ 2018/11/18\\)修改了\\(Letex\\)，其他没有变中间我\\(AFO\\)了,成功从红名掉到了蓝名 \\(update

约定不等于承诺〃/ 2021年10月26日 21:20/ 0 赞/ 336 阅读

相关【题解】P2710 数列

> 区间操作集大成者……？ > 可能吧…… by某位不愿意透露姓名的巨学 \\\ 本题需要实现： INSERT DELETE REVERSE

秒速五厘米/ 2021年10月26日 12:00/ 0 赞/ 280 阅读

相关【题解】Luogu P2257 YY的GCD

[原题传送门][Link 1] 这题需要运用[莫比乌斯反演(懵逼钨丝繁衍)][Link 2] 显然题目的答案就是\\\[ Ans=\\sum\_\{i=1\}^N

た入场券/ 2021年10月01日 06:44/ 0 赞/ 218 阅读

相关题解 P3954 【成绩】

[题面][Link 1] 这题显然可以用到线段树区间求和上代码： include<bits/stdc++.h> using namespace std; d

迷南。/ 2021年09月30日 10:06/ 0 赞/ 247 阅读

相关 HDU - 2504- 又见GCD【数论+gcd 】题解

目录 1.题目 2.代码 1.题目有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a

逃离我推掉我的手/ 2021年07月25日 00:03/ 0 赞/ 317 阅读