BZOJ 2693 jzptab ——莫比乌斯反演

同BZOJ 2154 但是需要优化

$ans=\sum_{d<=n}d*\sum_{i<=\lfloor n/d \rfloor} i^2 *\mu(i)* Sum(\lfloor \frac {n}{i*d} \rfloor,\lfloor \frac {m}{i*d} \rfloor)$

如果我们设$T=i*d$

$ans=\sum_{T<=n} Sum(\lfloor \frac {n}{T}\rfloor,\lfloor \frac {m}{T}\rfloor)\sum_{i \mid T} T*i*\mu(i)$

如果我们能计算出 $\sum_{i \mid T} T*i*\mu(i)$的前缀和我们就可以在\Theta (n)的时间内解决这个问题

它是积性函数，当$pr[j] \nmid i$的时候，新加入的$pr[j]$对$\mu$没有贡献（均为0）只有$T$的部分发生了改变所以乘一个$pr[j]$就可以了

然后就可以$\Theta (T\sqrt n)$解决了

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define md 100000009

#define maxn 10000005

int n,m,t,h[maxn],pr[maxn],top=0;

bool vis[maxn];

void init()

{

    memset(vis,false,sizeof vis);

    h[1]=1;

    F(i,2,maxn-1)

    {

        if (!vis[i])

        {

            pr[++top]=i;

            h[i]=((i-(ll)i*i)%md+md)%md;

        }

        F(j,1,top)

        {

            if ((ll)i*pr[j]>=maxn) break;

            vis[i*pr[j]]=true;

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

            {

                h[i*pr[j]]=((ll)h[i]*pr[j])%md;

                break;

            }

            h[i*pr[j]]=((ll)h[i]*h[pr[j]])%md;

        }

    }

    F(i,2,maxn-1)

        h[i]=((ll)h[i-1]+h[i])%md;

}

ll Sum(int n,int m)

{

    n%=md; m%=md;

    n=((ll)n*(n+1)/2)%md;

    m=((ll)m*(m+1)/2)%md;

    return ((ll)n*m)%md;

}

void solve(int n,int m)

{

    if (n>m) swap(n,m);

    ll ret=0;

    for (int i=1,last=0;i<=n;i=last+1)

    {

        last=min(n/(n/i),m/(m/i));

        ret=(ret+((ll)h[last]-h[i-1])*Sum(n/i,m/i))%md;

    }

    ret+=md; ret%=md;

    printf("%lld\n",ret);

}

int main()

{

    init();

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d%d",&n,&m);

        solve(n,m);

    }

}

巴特西

BZOJ 2693 jzptab ——莫比乌斯反演

最新文章

热门文章