hdu4746:2013杭州网络赛I 莫比乌斯反演

题意：

有5000组询问，每组询问求有多少i,j满足i∈[1,n]，j∈[1,m]且gcd(i,j)的质因子数目<=p。 n,m<=500000

思路：

首先预处理出每个数的质因子数目分别等于多少，则问题转化为求给定区间内，gcd等于某一堆数的i,j有多少组

发现很像一个基础莫比乌斯反演题：hdu1695。但是此题在某组询问中可能要处理很多个gcd，所以需要进行一些预处理

我们首先筛出每个数的莫比乌斯函数和它的质因子个数

通过容斥的公式可以看出如果要求的gcd为d，那么d*i的倍数对答案的贡献为 mobi[i]。

这样就可以预处理出每个p对应位置的莫比乌斯函数系数之和p[19][500000]

注意这里容易想到p是小于等于18的，因为50W之内的数最多有18个质因子(2^19>500000)

然后对p数组求前缀和，可以使单组查询复杂度变为p*sqrt(n)，具体为什么是分块sqrt(n)可以参考hdu1695的题解。交了一发超时了。。

还以为写搓了，后来发现可以再求一次前缀和。。这样单组查询变成了sqrt(n)，终于过了

代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int mb[maxn+];

 int notprime[maxn+];

 int num[maxn+];

 int prime[maxn];

 vector<int>v[];

 int np=;

 void setprime()

 {

     memset(notprime,,sizeof(notprime));

     mb[]=;

     num[]=;

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

     {

         if(!notprime[i])

         {

             prime[np++]=i;

             num[i]=;

             mb[i]=-;

         }

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

         {

             notprime[i*prime[j]]=;

             num[i*prime[j]]=num[i]+;

             //v[num[i]+1].push_back(i*prime[j]);

             if(i%prime[j]==)

             {

                 mb[i*prime[j]]=;

                 break;

             }

             else

             {

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

             }

         }

     }

 }

 int p[][];

 int sum[][];

 int f[][];

 int main()

 {

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

     setprime();

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

     {

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

         {

             p[num[i]][i*j]+=mb[j];

         }

     }

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

     {

         sum[i][]=;

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

         {

             sum[i][j]=sum[i][j-]+p[i][j];

         }

     }

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

     {

         f[][i]=sum[][i];

         for(int j=;j<=;j++)

         {

             f[j][i]=f[j-][i]+sum[j][i];

         }

     }

     int n,m,k,q;

     scanf("%d",&q);

     while(q--)

     {

         long long ans=;

         scanf("%d%d%d",&n,&m,&k);

         if(k>)

         {

             printf("%I64d\n",(long long)n*m);

             continue;

         }

         if(n>m)

             swap(n,m);

         for(int j=; j<=n; j++)

         {

             int to=min(n/(n/j),m/(m/j));

             ans+=(long long)(n/j)*(m/j)*(f[k][to]-f[k][j-]);

             j=to;

         }

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

     }

     return ;

 }

巴特西

hdu4746:2013杭州网络赛I 莫比乌斯反演

最新文章

热门文章