首页 > 代码库 > BZOJ2045: 双亲数

BZOJ2045: 双亲数

2024-07-24 20:06:14   217人阅读

2045: 双亲数

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 602  Solved: 275
[Submit][Status]

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”全国竞赛

题解：

POI ZAP的弱化版，不用分块，线性筛+枚举即可。

代码：

 1 #include<cstdio> 2  3 #include<cstdlib> 4  5 #include<cmath> 6  7 #include<cstring> 8  9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 1000000+100026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline ll read()48 49 {50 51     ll x=0,f=1;char ch=getchar();52 53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57     return x*f;58 59 }60 ll n,m,d,mx,tot,mu[maxn],p[maxn];61 bool check[maxn];62 63 int main()64 65 {66 67     freopen("input.txt","r",stdin);68 69     freopen("output.txt","w",stdout);70 71     n=read();m=read();d=read();n/=d;m/=d;72     mu[1]=1;mx=min(n,m);73     for2(i,2,mx)74     {75         if(!check[i]){p[++tot]=i;mu[i]=-1;}76         for1(j,tot)77         {78             int k=i*p[j];79             if(k>mx)break;80             check[k]=1;81             if(i%p[j]==0){mu[k]=0;break;}82             else mu[k]=-mu[i];83         }84     }85     ll ans=0;86     for1(i,mx)ans+=mu[i]*(n/i)*(m/i);87     printf("%lld\n",ans);    88 89     return 0;90 91 }
View Code

 

BZOJ2045: 双亲数


联系
我们