BZOJ2045: 双亲数

2023-08-21 11:57:28

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

【样例解释】

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

HINT

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

Source

第一届“NOIer”全国竞赛

题解：

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

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000000+1000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline ll read()

 {

     ll x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 ll n,m,d,mx,tot,mu[maxn],p[maxn];

 bool check[maxn];

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();d=read();n/=d;m/=d;

     mu[]=;mx=min(n,m);

     for2(i,,mx)

     {

         if(!check[i]){p[++tot]=i;mu[i]=-;}

         for1(j,tot)

         {

             int k=i*p[j];

             if(k>mx)break;

             check[k]=;

             if(i%p[j]==){mu[k]=;break;}

             else mu[k]=-mu[i];

         }

     }

     ll ans=;

     for1(i,mx)ans+=mu[i]*(n/i)*(m/i);

     printf("%lld\n",ans);    

     return ;

 }

码农公寓