记录编号	196675	评测结果	AAAAAAAAAA
题目名称	双亲数	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2015-10-22 07:01:03	内存使用	32.72 MiB

#define MAXN 2000010UL

#define ll long long

#include <cstdio>

ll pri[MAXN],n,m,k,mu[MAXN],Ans,r;
bool isp[MAXN];

int main(){
	freopen("parents.in","r",stdin);freopen("parents.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	if(n>m) n^=m,m^=n,n^=m;mu[1]=1;r=n/k;
	for(ll i=2;i<=r;i++){
		if(!isp[i]) pri[++pri[0]]=i,mu[i]=-1;
		for(ll j=1,x;j<=pri[0]&&i*pri[j]<=r;j++){
			x=i*pri[j];isp[x]=true;
			if(i%pri[j]) mu[x]=-mu[i];
			else{mu[x]=0;break;}
		}
	}
	for(ll i=1;i<=r;i++) Ans+=mu[i]*(n/(i*k))*(m/(i*k));
	printf("%lld",Ans);return 0;
}