题解洛谷P2568 GCD

约定不等于承诺〃 2021-10-26 21:20 427阅读 0赞

\$update\\ \\ \\ 2018/11/18\$修改了\$Letex\$，其他没有变

中间我\$AFO\$了,成功从红名掉到了蓝名

\$update 2019/7/22\$加了很多自己学文化课时的感悟

--------------------

听说有一句话数论只会\$GCD\$，所以我翻开了此题，却发现这题并不是这么简单

所以就写篇题解吧(废话真多)

[题目][Link 1]

--------------------

先介绍一个东西：欧拉函数

定义： 对于正整数\$n\$,小于或等于\$n\$,且与\$n\$互质的正整数(包括1)的个数，记作\$φ(n)\$。(\$φ(1)=1\$)

写成数学公式就是\$φ(n)=\\displaystyle\\sum\_\{i=1\}^n1(gcd(i,n)=1)\$

那么答案是什么呢？

我们考虑每个质数\$p\$对答案的贡献,对于每一个质数\$p\$

\$gcd(x,y)=1\$等价于\$gcd(a\*p,b\*p)=p\$

所以\$gcd(x,y)\$为\$p\$的数对个数即为\$1<=a,b<= \\frac\{n\}\{p\}\$中互质对\$a,b\$的个数,其中不妨令\$a<=b\$

对于每一个\$b,a\$有\$φ(b)\$个取值使\$a,b\$互质，及\$gcd(a\*p,b\*p)=p\$

所以此题答案就是\$\\displaystyle\\sum\_\{i=1\}^n φ(i)\$

--------------------

先介绍一些\$φ(n)\$的性质：

积性函数(常见的有)

$ε(n)=\[n==1\]        d(n)=\\displaystyle\\sum\_\{d|n\}1       σ(n)=\\displaystyle\\sum\_\{d|n\}d $

$ μ(n)=\[max(c\_1,c\_2,...c\_m)<=1\]\*(-1)^m$

当然，还有\$φ(n)\$喽

积性函数的性质：若\$gcd(a,b)==1\$则\$f(a\\times b)=f(a)\\times f(b)\$

\$φ(n)\$的其他性质

1.若\$p\$为质数\$φ(p)=p-1\$

2.若\$p|n\$且\$p^2|n\$，则\$φ(n)=φ(n/p)\\times p\$

3.若\$p|n\$但是不满足\$p^2|n\$，则\$φ(n)=φ(n/p)\\times (p-1)\$

4.\$\\displaystyle\\sum\_\{d|n\}φ(d)=n\$

--------------------

所以，现在问题就转化为了怎样快速求\$φ(n)\$

可以联想到欧拉筛法，因为可以在\$O(n)\$的时间内求出所有质数。

若对于\$i\$，如果已知所有的\$1-i\$ 的\$φ\$，枚举\$<=i\$的质数\$p\[j\]\$，可以求得\$φ(x\\times p\[j\])\$

1.若\$p\[j\]\$与\$x\$互质 \$φ(x\*p\[j\])=φ(x)\*φ(p\[j\])\$

2.若不互质，设\$x=t\*p\[j\]^k\$

\$φ(x\*p\[j\])=φ(t\*p\[j\]^\{k+1\})=φ(t)\*φ(p\[j\]^\{k+1\})\$\$=φ(t)\*φ(p\[j\]^k)\*p\[j\]=φ(x)\*p\[j\]\$

所以，预处理\$φ(i)\$的代码：

for (int i=2;i<=n;++i){ if (is_prime[i]) phi[i]=i-1,prime[++prime_num]=i; for (int j=1;j<=prime_num&&prime[j]*i<=n;++j){ is_prime[prime[j]*i]=0; if (__gcd(prime[j],i)==1) phi[prime[j]*i]=phi[prime[j]]*phi[i]; else phi[prime[j]*i]=prime[j]*phi[i]; if (i%prime[j]==0) break; } }

做一下前缀和就可以了

最后提醒一句，\$10\$年\$OI\$一场空，不开\$long\\ long\$见祖宗

--------------------

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=10000005; bool is_prime[N]; int n,prime_num,prime[N],phi[N]; long long sum[N]; int main(){ scanf("%d",&n); memset(is_prime,1,sizeof(is_prime)); is_prime[1]=0;phi[1]=1; for (int i=2;i<=n;++i){ if (is_prime[i]) phi[i]=i-1,prime[++prime_num]=i; for (int j=1;j<=prime_num&&prime[j]*i<=n;++j){ is_prime[prime[j]*i]=0; if (__gcd(prime[j],i)==1) phi[prime[j]*i]=phi[prime[j]]*phi[i]; else phi[prime[j]*i]=prime[j]*phi[i]; if (i%prime[j]==0) break; } } for (int i=1;i<=n;++i) sum[i]=sum[i-1]+phi[i]; long long ans=0; for (int i=1;i<=prime_num&&prime[i]<=n;++i) ans+=(sum[n/prime[i]]<<1)-1; printf("%lld\n",ans); return 0; }

转载于:https://www.cnblogs.com/zhouykblog/p/11227818.html

[Link 1]: https://www.luogu.org/problemnew/show/P2568