hdu1695 GCD（莫比乌斯入门题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695

题意：

给出n、m、k ，求出1<=x<=n, 1<=y<=m 且gcd(x,y) == k 的（x,y）的对数

解析：

显然就是求 [1,n/k] 与 [1, m/k]有多少数对的最大公约数是1

莫比乌斯入门题

我们设

为满足且和的的对数

那么，很显然，反演后得到

我们所需要的答案便是 f(1) = ∑_i=1µ(i)*(n/i)*(m/i) ，求解这个式子我们可以分块求和，复杂度为O（√n）。

最后注意由于题目要求，需要将重复的去掉。

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int vis[maxn];

 int prime[maxn];

 int cnt;

 int mu[maxn];

 int sum[maxn];

 void init()

 {

     memset(vis,,sizeof(vis));

     cnt=;

     mu[]=;

     for(int i=;i<maxn;i++)

     {

         if(!vis[i])

         {

             prime[cnt++]=i;

             mu[i]=-;

         }

         for(int j=;j<cnt&&i*prime[j]<maxn;j++)

         {

             vis[i*prime[j]]=;

             if(i%prime[j])

                 mu[i*prime[j]]=-mu[i];

             else

             {

                 mu[i*prime[j]]=;

                 break;

             }

         }

     }

     sum[]=;

     for(int i=;i<maxn;i++)

         sum[i]=sum[i-]+mu[i];

 }

 int main()

 {

     int a,b,c,d,k;

     init();

     int T,ca=;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

         printf("Case %d: ",ca++);

         if(k==)

         {

             printf("0\n");

             continue;

         }

         b=b/k;

         d=d/k;

         if(b>d)

             swap(b,d);

         long long ans1=;

         int last;

         for(int i=;i<=b;i=last+)

         {

             last=min(b/(b/i),d/(d/i));

             ans1+=(long long)(sum[last]-sum[i-])*(b/i)*(d/i);

         }

         long long ans2=;

         for(int i=;i<=b;i=last+)

         {

             last=b/(b/i);

             ans2+=(long long)(sum[last]-sum[i-])*(b/i)*(b/i);

         }

         long long ans=ans1-ans2/;

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

     }

     return ;

 }

巴特西

hdu1695 GCD（莫比乌斯入门题）

最新文章

热门文章