hdu 4746 Mophues （莫比乌斯反演）

第二个样例： N=10,M=10,P=1 $N=10,M=10,P=1$

ans=f(1)+f(2)+f(3)+f(5)+f(7) $ans=f\left(1\right)+f\left(2\right)+f\left(3\right)+f\left(5\right)+f\left(7\right)$

每个 f $f$ 具体的值

以 F(n) $F\left(n\right)$ 来展示：
ans= $ans=$
F(1)∗μ(1)+ $F\left(1\right)\ast \mu \left(1\right)+$
F(2)∗[μ(1)+μ(2)]+ $F\left(2\right)\ast \left[\mu \right(1)+\mu (2\left)\right]+$
F(3)∗[μ(1)+μ(3)]+ $F\left(3\right)\ast \left[\mu \right(1)+\mu (3\left)\right]+$
F(4)∗[μ(1)+μ(2)+μ(4)]+ $F\left(4\right)\ast \left[\mu \right(1)+\mu (2)+\mu (4\left)\right]+$
F(5)∗[μ(1)+μ(5)]+ $F\left(5\right)\ast \left[\mu \right(1)+\mu (5\left)\right]+$
F(6)∗[μ(1)+μ(2)+μ(3)+μ(6)]+ $F\left(6\right)\ast \left[\mu \right(1)+\mu (2)+\mu (3)+\mu (6\left)\right]+$
F(7)∗[μ(1)+μ(7)] $F\left(7\right)\ast \left[\mu \right(1)+\mu (7\left)\right]$
F(8)∗[μ(1)+μ(2)+μ(4)+μ(8)]+ $F\left(8\right)\ast \left[\mu \right(1)+\mu (2)+\mu (4)+\mu (8\left)\right]+$
F(9)∗[μ(1)+μ(3)+μ(9)]+ $F\left(9\right)\ast \left[\mu \right(1)+\mu (3)+\mu (9\left)\right]+$
F(10)∗[μ(1)+μ(2)+μ(5)+μ(10)] $F\left(10\right)\ast \left[\mu \right(1)+\mu (2)+\mu (5)+\mu (10\left)\right]$

阔以发现：每个 F(n) $F\left(n\right)$ 都有一个由 μ $\mu$ 组成的系数，并且这几个 μ $\mu$ 的值都是 n $n$ 的因子（为啥会是这样我也没懂~）

我们用 sum[n] $sum\left[n\right]$ 来表示 F(n) $F\left(n\right)$ 的这个系数的和

那怎么求这 n $n$ 个 sum $sum$ 喃？遍历一次 n $n$ 然后再找每个 n $n$ 的因子？那显然是要不得的

我们只需要从 1 $1$ 到 n $n$ 遍历一遍，然后看每个数作为因子，把他作为因子的贡献加到相应的地方就行了

for(int i=1;i<=N;i++)
{
    for(int j=i;j<=N;j+=i)
    {
        sum[j]+=mu[j/i];
    }
}

而这道题还有个条件，就是他的质因子的个数要小于 P $P$ ，数据范围是 5e5 $5e5$ 因此，最小的质因子 2 $2$ ，最多 19 $19$ 个 2 $2$ 都已经达到了 5e5 $5e5$，因此质因子的个数一定是小于等于 19 $19$ 的
因此我们再多加一维，用 sum[j][num(i)] $sum\left[j\right]\left[num\right(i\left)\right]$ 来表示， num[i] $num\left[i\right]$ 是 i $i$ 的质因子个数

/* *********** 未分块加速版本 *********** 这个是没有分块加速的，我跑个300w的Q，速度也没跟加速的差好多呀，但是就是T了。。。 */
#include"bits/stdc++.h"
//#include"iostream"
using namespace std;
const int maxn=5e5+5;
char mu[maxn];
vector<int>prime;
bool vis[maxn];
int sum[maxn][20];//sum[i][j]表示i的所有因子的莫比乌斯函数之和
int num[maxn];//i的质因子个数
int N,M,P;
void Init(int NN)
{
    memset(vis,1,sizeof(vis));
    memset(num,0,sizeof(num));
    mu[1]=1;
    for(int i=2;i<=NN;i++)
    {
        if(vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
            num[i]=1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=NN;j++)
        {
            vis[i*prime[j]]=0;
            num[i*prime[j]]=num[i]+1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else mu[i*prime[j]]=-mu[i];
        }
    }
}
int main()
{
    Init(500000);
    memset(sum,0,sizeof(sum));
    for(int i=1;i<maxn;i++)//求因子i的所有贡献，但是分布到了20个维度上去了，因此下一步还要把他们加回来
    {
        for(int j=i;j<maxn;j+=i)
        {
            sum[j][num[i]]+=mu[j/i];
        }
    }
    for(int i=1;i<maxn;i++)//把分散的都加回来
    {
        for(int j=1;j<20;j++)sum[i][j]+=sum[i][j-1];
    }
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%d%d%d",&N,&M,&P);
        if(P>=20)
        {
            cout<<(long long)N*M<<endl;
            continue;
        }
        if(N>M)swap(N,M);
        long long ans=0;
        for(int i=1;i<=N;i++)
        {
            ans+=sum[i][P]*(N/i)*(M/i);
        }
        printf("%lld\n",ans);
    }
}