首页 > 代码库 > BZOJ 2045: 双亲数

BZOJ 2045: 双亲数

2024-09-04 23:10:08   219人阅读

2045: 双亲数

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 848  Solved: 406
[Submit][Status][Discuss]

Description

小D是一名数学爱好者，他对数字的着迷到了疯狂的程度。 我们以d = gcd(a, b)表示a、b的最大公约数，小D执著的认为，这样亲密的关系足可以用双亲来描述，此时，我们称有序数对(a, b)为d的双亲数。 与正常双亲不太相同的是，对于同一个d，他的双亲太多了 >_< 比如，(4, 6), (6, 4), (2, 100)都是2的双亲数。 于是一个这样的问题摆在眼前，对于0 < a <= A, 0 < b <= B，有多少有序数对(a, b)是d的双亲数？

Input

输入文件只有一行，三个正整数A、B、d (d <= A, B)，意义如题所示。

Output

输出一行一个整数，给出满足条件的双亲数的个数。

Sample Input







5 5 2

Sample Output

3


【样例解释】

满足条件的三对双亲数为(2, 2) (2, 4) (4, 2)

HINT

对于100%的数据满足0 < A, B < 10^ 6

Source

第一届“NOIer”全国竞赛

分析：

好久不写数学了...水一发...

$\sum_ {i=1}^{n} \sum_ {j=1}^{m} [gcd(i,j)==k]$

$n=n/k,m=m/k(n<=m)$

$\sum_ {i=1}^{n} \sum_ {j=1}^{m} [gcd(i,j)==1]$

$\sum_ {i=1}^{n} \sum_ {j=1}^{m} \sum_ {d\mid gcd(i,j)} μ(d)$

$\sum_ {d=1}^{n} μ(d) \left\lfloor \frac{n}{d} \right \rfloor \left\lfloor \frac{m}{d} \right \rfloor$

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>//by NeighThorn#define int long longusing namespace std;const int maxn=1000000+5;int n,m,d,k,cnt,mu[maxn],pri[maxn],vis[maxn];inline void prework(void){	mu[1]=1; 	for(int i=2;i<=1000000;i++){		if(!vis[i])			pri[++cnt]=i,mu[i]=-1;		for(int j=1;j<=cnt&&pri[j]*i<=1000000;j++){			vis[pri[j]*i]=1;			if(i%pri[j]==0){				mu[i*pri[j]]=0;				break;			}			mu[i*pri[j]]=-mu[i];		}		mu[i]+=mu[i-1];	}}signed main(void){	scanf("%lld%lld%lld",&n,&m,&d);	n/=d,m/=d;if(n>m) swap(n,m);prework();	int ans=0,r;	for(int i=1;i<=n;i=r+1){		r=min(n/(n/i),m/(m/i));		ans+=(mu[r]-mu[i-1])*(n/i)*(m/i);	}	printf("%lld\n",ans);	return 0;	}

　　

By NeighThorn

BZOJ 2045: 双亲数


联系
我们