HDU 4746 Mophues（莫比烏斯反演 + 數論）

一道比較簡單的反演，随便推推式子玩玩。

大緻題意：求

，其中f(x)表示x分解質因子後，質因子的指數之和。

看到gcd，慣例還是把gcd的結果提取出來計算個數。

右邊那個東西顯然是一個可以反演的東西，這裡我們直接跳過一些重複的過程，直接給出反演之後的結果：

考慮交換求和次序：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)

using namespace std;

const int N = 5e5 + 10;

int mu[N],p[N],t[N],s[20][N],sz;
bool isp[N];

void init()
{
    mu[1]=1,t[1]=0;
    for(int i=2;i<N;i++)
    {
        if(!isp[i]) mu[i]=-1,t[i]=1,p[++sz]=i;
        for(int j=1;j<=sz&&i*p[j]<N;j++)
        {
            isp[i*p[j]]=1;
            t[p[j]*i]=t[i]+1;
            if(i%p[j]==0)
            {
                mu[p[j]*i]=0; break;
            } else mu[p[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<N;i++)
        for(int j=i;j<N;j+=i)
            s[t[i]][j]+=mu[j/i];
    for(int k=1;k<20;k++)
        for(int i=1;i<N;i++)
            s[k][i]+=s[k-1][i];
    for(int k=0;k<20;k++)
        for(int i=1;i<N;i++)
            s[k][i]+=s[k][i-1];
}

int main()
{
    init();
    int T; sc(T);
    while(T--)
    {
        LL ans=0;
        int n,m,p;
        sccc(n,m,p);
        if (p>=20)
        {
            printf("%lld\n",(LL)m*n);
            continue;
        }
        if (n>m) swap(n,m);
        for(int l=1,r;l<=n;l=r+1)
        {
            LL a=n/l,b=m/l;
            r=min(n/a,m/b);
            ans+=a*b*(s[p][r]-s[p][l-1]);
        }
        printf("%lld\n",ans);
    }
}