记录编号	24605	评测结果	AAAAAAAAAA
题目名称	双亲数	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	1.993 s
提交时间	2011-04-12 19:31:38	内存使用	7.89 MiB

#include <iostream>

using namespace std;

long long A,B,i,j,d,k1,k2,f[1000002];

int main()
{
	freopen("parents.in","r",stdin);
	freopen("parents.out","w",stdout);
	scanf("%d%d%d",&A,&B,&d);
	k1=A/d;
	k2=B/d;
	if (k1>k2) swap(k1,k2);
	f[k1]=k2/k1;
	for (i=k1-1;i>=1;i--)
	{
		f[i]=(k2/i)*(k1/i);
		if (k2/(i+1)==k2/i && k1/(i+1)==k1/i) 
		{
			f[i]=f[i+1];
			continue;
		}
		for (j=i*2;j<=k1;j+=i)
			f[i]-=f[j];
	}
	cout<<f[1]<<endl;
	return 0;
}