Darkbzoj 2818 Gcd

链接：https://darkbzoj.tk/problem/2818

---

规定 \([x]\) 为逻辑判断函数，若 \(x\) 为真则 \([x]=1\)，否则 \([x]=0\) 。

这题要我们统计的是：

\[\sum_{i=1}^{m}\sum_{j=1}^{\lfloor\frac{n}{p_i} \rfloor}\sum_{k=1}^{\lfloor\frac{n}{p_i}\rfloor}[gcd(j,k)=1] \]

我们可以用莫比乌斯反演化简成：

\[\sum_{i=1}^m\sum_{d=1}^{p_i}\mu(d)\times\lfloor\frac{n}{x}\rfloor^2 \]

但是这样子我们的复杂度是 \(O(n^2)\) 的，我们考虑换一种式子的化简方式。我们考虑如何快速求出 \(gcd(x,y)=p\;(x\le n,y\le n)\) 的个数。

个数为：

\[\begin{aligned} Ans&=\sum_{i=1}^{\lfloor\frac{n}{p} \rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[gcd(i,j)=1] \\ &=-1+2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}{\sum_{j=1}^{i}[gcd(i,j)=1]} \\ &=-1+2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor} \varphi(i) \end{aligned} \]

解释一下式子，如果 \(gcd(i,j)=1\) 那么一定有 \(gcd(j,i)=1\)，所以 \(j\) 只用累计到 \(i\) 就好了，那么 \(\sum_{j=1}^{i}[gcd(i,j)=1]\) 这个式子显然就是 \(\varphi(i)\) 。又因为 \(gcd(1,1)\) 会重复统计 \(1\) 次，所以需要减掉。化简出来的这个式子我们可以用前缀和做到 \(O(n)\) 预处理，\(O(1)\) 查询。欧拉函数和质数也可以用欧拉筛在 \(O(n)\) 的时间内求出。

所以我们只用枚举 \(n\) 之内的质数，然后 \(O(1)\) 查询即可。

总时间复杂度为 \(O(n)\)

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e7+5;
int pc,prime[MAXN],p[MAXN],n;
ll phi[MAXN];
int main()
{
	scanf("%d",&n);
	phi[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!p[i]) prime[++pc]=i,phi[i]=i-1;
		for(int j=1;j<=pc&&1ll*i*prime[j]<=n;++j)
		{
			p[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
	for(int i=1;i<=n;++i) phi[i]+=phi[i-1];
	ll ans=0;
	for(int i=1;i<=pc;++i)
		ans+=2*phi[n/prime[i]]-1;
	printf("%lld\n",ans);
	return 0;
}