记录编号	56501	评测结果	AAAAAAAAAA
题目名称	双亲数	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.510 s
提交时间	2013-03-31 09:59:54	内存使用	20.44 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("parents.in");
ofstream fout("parents.out");
const long long Mn=2000000;
long long mu[Mn],A,B,d;
bool P[Mn];
void init()
{
	fin>>A>>B>>d;
long long i,j,Max=max(A,B);
	for(i=1;i<=Max;i++)
		mu[i]=1;
	for(i=2;i<=Max;i++)
	{
		if(P[i])continue;
		mu[i]=-1;
			for(j=i+i;j<=Max;j+=i)
			{
				P[j]=true;
				if(j/i%i==0)
					mu[j]=0;
				else
					mu[j]*=-1;
			}
	}
	mu[1]=1;
}
void fig(long long a,long long b)
{
long long i,Min=min(a,b),Ans=0;
	for(i=1;i<=Min;i++)
		Ans+=mu[i] * (a/i)*(b/i);
	fout<<Ans<<endl;
}
long long gcd(long long a,long long b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main(){
	init();//读入以及计算Mobius函数
	fig(A/d,B/d);/*
long long i,j,Sum=0;
	for(i=1;i<=A/d;i++)
		for(j=1;j<=B/d;j++)
			if(gcd(i,j)==1)
			{
		//		fout<<i<<" "<<j<<endl;
				Sum++;
			}
		fout<<Sum;*/
	fin.close();
	fout.close();
	return 0;
}