【BZOJ2818】Gcd

题面

题目分析

莫比乌斯反演模板题。

假设要求(gcd(x,y)==k)的数对的对数，即(gcd(frac{x}{k},frac{y}{k})==1)的数对的对数。

(以下(x,y,n)均视为除以(k)之后)

设(f[i])为(gcd(x,y)==i)的对数，(g[i])为(gcd(x,y)==xi)的对数，其中(xin Z)。

显然，(g[i]=(n/i)*(n/i))

有(g[x]=sumlimits_{x|d}^nf[d])，然后，你惊喜地发现，这就是莫比乌斯反演的模板。

所以(f[x]=sumlimits_{x|d}^nmu(frac{d}{x})*g[d])，直接计算即可。

代码实现

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=10000005;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
int mu[N],prime[N]; 
bool vis[N];

int main(){
	int n=Getint();
	mu[1]=1;
	for(int i=2;i<n;i++){
		if(!vis[i])prime[++prime[0]]=i,mu[i]=-1;
		for(int j=1;j<=prime[0]&&i*prime[j]<n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
			mu[i*prime[j]]=-mu[i];
		}
	}
	LL ans=0;
	for(int i=1;i<=prime[0];i++)
		for(int j=1;j*prime[i]<=n;j++)
			ans+=(LL)mu[j]*(n/j/prime[i])*(n/j/prime[i]);
	cout<<ans;
	return 0;
}

P.S

加强版：【BZOJ2820】YY的GCD