BZOJ3309 DZY Loves Math（莫比乌斯反演+线性筛）

　　一通正常的莫比乌斯反演后，我们只需要求出g(n)=Σf(d)*μ(n/d)的前缀和就好了。

　　考虑怎么求g(n)。当然是打表啊。设n=∏p，n/d=∏p。显然若存在b>1则这个d没有贡献。考虑b为0和1两种情况。如果只看a最小的质因子的选取情况，会发现大部分情况下其是0还是1，对f的取值是没有影响的，但会使μ取反，于是就抵消为0。而特殊情况即为所有a均相同，此时若所有b都取1会使f减少。与一般情况比较可以得到此时g(n)=(-1)。

　　然后就可以线性筛了。记录一下n去掉最小质因子后的数及最小质因子的幂次就可以了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 10000010

int T,prime[N],f[N],p[N],c[N],v[N],cnt=;

bool flag[N];

int main()

{

#ifndef ONLINE_JUDGE

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

    freopen("bzoj3309.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    flag[]=1;p[]=;c[]=;f[]=;

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

    {

        if (!flag[i]) prime[++cnt]=i,p[i]=,c[i]=,f[i]=;

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

        {

            int t=prime[j]*i;

            flag[t]=;

            if (i%prime[j]==)

            {

                p[t]=p[i];

                c[t]=c[i]+;

                if (c[p[i]]==) f[t]=;

                else f[t]=(c[t]==c[p[i]]?-f[p[i]]:);

                break;

            }

            p[t]=i;

            c[t]=;

            if (c[i]==) f[t]=;

            else f[t]=(c[i]==?-f[i]:);

        }

    }

    for (int i=;i<=N-;i++) f[i]+=f[i-];

    while (T--)

    {

        int n=read(),m=read();

        long long ans=;

        for (int i=;i<=min(n,m);i++)

        {

            int t=min(n/(n/i),m/(m/i));

            ans+=1ll*(f[t]-f[i-])*(n/i)*(m/i);

            i=t;

        }

        printf(LL,ans);

    }

    return ;

}