bzoj 2818 Gcd 欧拉函数求和

本文主要是介绍bzoj 2818 Gcd 欧拉函数求和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

Sample Output

4
HINT

hint

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

传送门
woc666还有这种坑。。。
（啥坑待会儿讲啦）

看看这道题，看到gcd就有种莫比乌斯繁衍(划掉)的恐慌感。。
然而坚定的我还是想了想。。
首先n有10^7，假设枚举了x,y中的任意一个基本就得O(1)了。。
所以我就没考虑枚举x或者y。
令z=gcd(x,y)，则z为质数。
考虑枚举这个z，因为10^7中质数的数量只有不到50W个，所以很有前途= =
那么由于gcd(x,y)=z，我们要统计这种(x,y)的对数，
那么令：

x = z * A y = z * B

$x=z*A\\ y=z*B\\$
根据要求，gcd(A,B)=1，也就是说假设我们枚举了A，
那么B的个数就是和A互质的数字的个数了。
为了方便，我们假设B<=A，只要最后计算一下就好了。
于是，当我们枚举了这个z，B的范围自然是

1<=B<=n/z $1<=B<=n/z$ 了，
那么z的贡献就是

\sum ϕ (i) ， 1 < = i < = n / z

$\sum \phi(i)，1<=i<=n/z$
也就是说，这是一个欧拉函数求和。
那么只要线性筛一下欧拉函数，然后弄个前缀和，
每次就可以直接统计贡献了。时间复杂度O(N+P)，P是n内质数个数。
那么这个求出来之后，再*2，没有了遗漏，但有没有重复呢？
显然是有的，比如gcd(3,3)=3是个质数，但是3=3，所以乘2的话就会被计算2遍，
但也很容易看出被计算2遍的一定是gcd(x,x)=x，x是个质数，
所以最后答案再减去P即可。

来吐槽一个坑。。。。
对于ans，求出的是ans*2-P……
然而……ans*2要爆long long的！QAQ
我一开始80，非常恶心。。
于是就只好写成(ans-P)*2+P的形式了……因为最后没有爆long long。。
靠又没有1A啊啊抓狂。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,pcnt;
ll phi[10000001],prime[500000];
bool notprime[10000000];
void get_eula_prime(){notprime[1]=1,pcnt=0;phi[1]=1LL;for (int i=2;i<=n;i++){if (!notprime[i]) phi[i]=(ll)i-1,prime[++pcnt]=(ll)i;for (int j=1;j<=pcnt;j++){if (i*prime[j]>n) break;notprime[i*prime[j]]=1;if (i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;} else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}for (int i=2;i<=n;i++) phi[i]+=phi[i-1];
}
int main(){scanf("%d",&n);get_eula_prime();ll ans=0LL;for (int i=1;i<=pcnt;i++) ans+=phi[n/prime[i]];ans-=(ll)pcnt;ans<<=1LL;ans+=(ll)pcnt;printf("%lld\n",ans);return 0;
}