POJ 3904

第一道莫比乌斯反演的题。

建议参看http://www.isnowfy.com/mobius-inversion/

摘其中部分

证明的话感觉写起来会比较诡异，大家意会吧
说一下这个经典题目：令R(M,N)=1≤x≤M,1≤y≤N中 gcd(x,y)=1 的个数
我们说G(z)表示gcd(x,y)是z的倍数的个数（以后都省略1≤x≤M,1≤y≤N的前提），换句话说z|gcd(x,y)的个数，那么很显然G(z)=⌊M/z⌋∗⌊N/z⌋，令F(z)表示gcd(x,y)=z的个数，

所以G(z)=∑(F(z)+F(2∗z)+F(3∗z)...)，于是我们得到F(z)=∑(G(z)∗μ(z)+G(2∗z)∗μ(2∗z)...)，从而得到了我们最终的答案ans=∑z≥1⌊M/z⌋∗⌊N/z⌋∗μ(z)

这里，只需要把z=1，通过求F（z）即可。

上面之所以成立，因为莫比乌斯的另一种形式（我未找到，但确实成立）

f(d) = ∑ g(n) (n % d == 0)

g(d) = ∑ mu[n / d] * f(n) (n %d == 0)

好像目前遇到的都是经典题目的类型了。。。

给出求莫比乌斯函数的代码：

void initial(){

	int i,j;

	for(i=1;i<N;i++) mobi[i]=1,vis[i]=false;

	for(i=2;i<N;i++) {

		if(vis[i]) continue;

		for(j=i;j<N;j+=i){

			vis[j]=true;

			if((j/i)%i==0){

				mobi[j]=0; continue;

			}

			mobi[j]=-mobi[j];

		}

	}

}

POJ 代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 10005

#define LL __int64

using namespace std;

int ID[N];

int mobi[N],cnt[N];

bool vis[N];

LL myc[N];

void initial(){

	int i,j;

	for(i=1;i<N;i++) mobi[i]=1,vis[i]=false;

	for(i=2;i<N;i++) {

		if(vis[i]) continue;

		for(j=i;j<N;j+=i){

			vis[j]=true;

			if((j/i)%i==0){

				mobi[j]=0; continue;

			}

			mobi[j]=-mobi[j];

		}

	}

	myc[0]=myc[1]=myc[2]=myc[3]=0;

	myc[4]=1;

	for(int i=5;i<N;i++)

	myc[i]=myc[i-1]*(LL)i/(LL)(i-4);  //这里求的其实是组合数

}

int main(){

	int n; int mx,tmp;

	initial();

	while(scanf("%d",&n)!=EOF){

		mx=-1;

		memset(ID,0,sizeof(ID));

		for(int i=0;i<n;i++){

			scanf("%d",&tmp);

			ID[tmp]++;

			mx=max(mx,tmp);

		}

		memset(cnt,0,sizeof(cnt));

		for(int i=1;i<=N;i++){

			for(int k=i;k<N;k+=i){

				if(ID[k])

				cnt[i]+=ID[k];

			}

		}

		LL ans=0;

		for(int i=1;i<=mx;i++){

			ans=ans+(LL)mobi[i]*myc[cnt[i]];

		}

		printf("%I64d\n",ans);

	}

	return 0;

}

巴特西

POJ 3904

最新文章

热门文章