bzoj 3309

奇怪的莫比乌斯反演...

题意：定义$f(n)$表示将$n$质因数分解后质因子的最高幂次，求$\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$

首先肯定是反演嘛...

推一发式子：

$\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$

$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{d=1}^{min(a,b)}[gcd(i,j)\equiv d]f(d)$

$\sum_{d=1}^{min(a,b)}f(d)\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)\equiv d]$

$\sum_{d=1}^{min(a,b)}f(d)\sum_{i=1}^{\frac{a}{d}}\sum_{j=1}^{\frac{b}{d}}[gcd(i,j)\equiv 1]$

$\sum_{d=1}^{min(a,b)}f(d)\sum_{i=1}^{\frac{a}{d}}\sum_{j=1}^{\frac{b}{d}}\sum_{t=1}^{min(\frac{a}{d},\frac{b}{d})}\mu(t)$

$\sum_{d=1}^{min(a,b)}f(d)\sum_{t=1}^{min(a,b)}\mu(t)\frac{a}{dt}\frac{b}{dt}$

令$T=dt$，得到：

$\sum_{T=1}^{min(a,b)}\frac{a}{T}\frac{b}{T}\sum_{d|T}f(d)\mu(\frac{T}{d})$

于是我们只需线性筛后面那一坨，然后数论分块即可

考虑线性筛：

令$g(T)=\sum_{d|T}f(d)\mu(\frac{T}{d})$

设对$T$进行质因数分解，得到这样的式子：$T=\prod_{i=1}^{n}p_{i}^{k_{i}}$

分两类进行讨论：

①.对任意$i\in [1,n-1]$，有$k_{i}=k_{i+1}$

首先我们考虑那个卷积式子，由于有一项是$\mu$，因此我们只需考虑$\mu$里面的东西无平方因子的情况，也即对于每个质因子，要么选$1$个，要么不选！

然后我们考虑什么分法会产生贡献：

不难发现，我们取奇数个质因子和取偶数个质因子的方案数是一样的，而其$\mu$互为相反数，当且仅当我们选了所有质因子时其$f$与其余的$f$不同（这个$f$变成了$k_{i}-1$），因此我们只需知道这个$-1$与对应的$\mu$产生的是正贡献还是负贡献即可，最后结论是$g(T)=(-1)^{n+1}$

②.存在$i,j\in [1,n]$，使得$k_{i}!=k_{j}$

类比上面的分析方式，得到$g(T)=0$

这样就可以线性筛了

代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

int mu[10000005];

int pri[1000005];

int f[10000005],mi[10000005],val[10000005];

ll F[10000005];

bool used[10000005];

int cnt=0;

ll T,x,y;

void init()

{

    mu[1]=1;

    f[1]=0;

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

    {

        if(!used[i])mu[i]=-1,pri[++cnt]=i,mi[i]=f[i]=1,val[i]=i;

        for(int j=1;j<=cnt&&i*pri[j]<=10000000;j++)

        {

            used[i*pri[j]]=1;

            if(i%pri[j]==0)

            {

                mu[i*pri[j]]=0;

                mi[i*pri[j]]=mi[i]+1;

                val[i*pri[j]]=val[i]*pri[j];

                ll temp=i/val[i];

                if(temp==1)f[i*pri[j]]=1;

                else f[i*pri[j]]=(mi[temp]==mi[i*pri[j]])?-f[temp]:0;

                break;

            }

            mu[i*pri[j]]=-mu[i],mi[i*pri[j]]=1,val[i*pri[j]]=pri[j],f[i*pri[j]]=(mi[i]==1)?-f[i]:0;

        }

    }

    for(int i=2;i<=10000000;i++)f[i]+=f[i-1];

}

ll solve(ll a,ll b)

{

    ll las=1,ans=0;

    for(int i=1;i<=a&&i<=b;i=las+1)

    {

        las=min(a/(a/i),b/(b/i));

        ans+=(f[las]-f[i-1])*(a/i)*(b/i);

    }

    return ans;

}

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

int main()

{

    init();

    read(T);

    while(T--)

    {

        read(x),read(y);

        printf("%lld\n",solve(x,y));

    }

    return 0;

}

巴特西

bzoj 3309

最新文章

热门文章