Mophues(莫比乌斯反演)

2018-08-20

Mophues

题意

若a的质因子个数<=P，则称a为p的一个lucky number。

给你n，m，P，求在n，m范围内的i，j，gcd(i,j)是P的lucky number，这样的i，j有几对？

n，m，P<=5e5。多组不超过5000组。

思路

题意就是让我们求：
$$
\sum_{i=1}^n\sum_{j=1}^mf(gcd(i,j)),其中f(x)表示x的质因子个数比p小
$$
反演过程就不具体写了，我们可以轻松得到结果：
$$
\sum_{t=1}^{min(n,m)}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{d|t}f(d)μ(\frac{t}{d})
$$
经过计算我们发现，5e5内的数字最大的质因数个数为18，那么对于大于18的p我们就可以降为18。

首先对5e5内的数预处理出它们的质因子个数。

然后枚举d，用sum[i][j]表示当t=i时，质因子个数为j的数的μ之和。

再对sum[i][j]求t=i时质因子个数小于等于j的μ之和。

然后对每一个t的sum求一个前缀和。

就可以分块做了。

注意ans和sum还是要开longlong。

看！代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
const int MOD=1e9+7;
/** 对于μ函数的线筛 */
int mu[N],prim[N];
bool vis[N]={0};
int cnt=0;
ll p[N]={0};
ll sum[N][21]={0};
void get_mu(int n)
{
	mu[1]=1;
	for(int i=2;i<=n;i++)
	{
    	if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
   	 	for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
        {
        	vis[prim[j]*i]=1;
        	if(i%prim[j]==0)break;
        	else mu[i*prim[j]]=-mu[i];
    	}
	}

}
void Solve(ll N)
{
    //int MAX=0;
    for(int n=1;n<=N;n++)
    {
        int tmp=n;
        for(ll i=1;prim[i]*prim[i]<=tmp; i++)
        {
            while(tmp%prim[i]==0) p[n]++,tmp/=prim[i];
        }
        if(tmp>1)
            p[n]++;  //这个不可以缺少
        //MAX=max(MAX,p[n]);
    }
    for(int d=1;d<=N;d++)
    {
        for(int k=1;k*d<=N;k++)
            sum[k*d][p[d]]+=mu[k];
    }
    for(int t=1;t<=N;t++)
    {
        for(int i=1;i<=18;i++)
            sum[t][i]+=sum[t][i-1];
    }
    for(int i=0;i<19;i++)
    {
        for(int t=1;t<=N;t++)
            sum[t][i]+=sum[t-1][i];
    }
}


int main()
{
    int t,n,m,u,v;
    get_mu(500000ll);
    Solve(500000ll);
    scanf("%d",&t);
    while(t--)
    {
        int n,m,P;
        scanf("%d%d%d",&n,&m,&P);
        if(P>18) P=18;
        int MIN=min(n,m);
        long long ans=0;
        for(int l=1,r;l<=MIN;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans+=1ll*(n/l)*(m/l)*(sum[r][P]-sum[l-1][P]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}