欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【BZOJ2693】jzptab(莫比乌斯反演)

程序员文章站 2022-07-01 16:30:16
不妨先设$n define N 10000010 define ll long long define mod 100000009 using namespace std; int t,n,m,cnt; ll prime[N],g[N],sum[N]; bool notprime[N]; void ......

不妨先设\(n<=m\)

把题目的柿子推一下:

\[\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\]

由于\(lcm(i,j)*gcd(i,j)=ij\)

\[=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\]

\(d=gcd(i,j)\),我们枚举\(d\),提到最前面,再枚举\(i\)\(d\)的几倍、\(j\)\(d\)的几倍。

\[=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\frac{(d\times i)\times (d\times j)}{d}[gcd((d\times i),(d\times j))=d]\]

则在上面这个柿子中,\((d\times i)\)为原来的\(i\)\((d\times j)\)为原来的\(j\)。将分式化简,\(gcd(d\times i,d\times j)=d\)里同时约掉一个\(d\)得:

\[=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}d\times i\times j[gcd(i,j)=1]\]

考虑到\(\sum_{i|n}\mu(i)=[n=1]\),代入\([gcd(i,j)=1]\)得:

\[=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} i\times j\sum_{k|gcd(i,j)}\mu(k)\]

我们再次枚举\(k\),提到\(\sum_{d=1}^n\)后:

\[=\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}i\times j[k|gcd(i,j)]\]

考虑到\([k|gcd(i,j)]\)即为\([k|i,k|j]\)

\[=\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i[k|i]\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}j[k|j] \tag{1}\]

这时我们先推另一个柿子:\(\sum_{i=1}^n[k|i]\),也就是询问\(1\)~\(n\)这些数中有多少个数是\(k\)的倍数,答案显然是\(\lfloor \frac{n}{k} \rfloor\)

但如果是求\(\sum_{i=1}^ni[k|i]\)呢?

也就是吧所有\(1\)~\(n\)中所有是\(k\)的倍数的数加起来,答案显然就是\[1\times k+2\times k+...+\lfloor \frac{n}{k} \rfloor \times k=(1+2+...+\lfloor \frac{n}{k} \rfloor)\times k=\frac{(1+\lfloor \frac{n}{k} \rfloor)\times \lfloor \frac{n}{k} \rfloor \times k}{2}\]

把这个代入\((1)\)

\[=\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\times\frac{(1+\lfloor \frac{\lfloor \frac{n}{d} \rfloor}{k} \rfloor)\times \lfloor \frac{\lfloor \frac{n}{d} \rfloor}{k} \rfloor \times k}{2}\times\frac{(1+\lfloor \frac{\lfloor \frac{m}{d} \rfloor}{k} \rfloor)\times \lfloor \frac{\lfloor \frac{m}{d} \rfloor}{k} \rfloor \times k}{2}\]

化简一下这个难看的柿子:

\[=\frac{1}{4}\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\times k^2\times(1+ \lfloor \frac{n}{dk} \rfloor)\times \lfloor \frac{n}{dk} \rfloor \times(1+ \lfloor \frac{m}{dk} \rfloor)\times \lfloor \frac{m}{dk} \rfloor\]

然后令\(t=dk\),我们枚举\(t\),并提到前面来。

\[\begin{aligned} & =\frac{1}{4}\sum_{t=1}^{n}(1+ \lfloor \frac{n}{t} \rfloor)\times \lfloor \frac{n}{t} \rfloor \times(1+ \lfloor \frac{m}{t} \rfloor)\times \lfloor \frac{m}{t} \rfloor\sum_{d|t}d\times\mu(\frac{t}{d})\times\frac{t^2}{d^2}\\ & =\frac{1}{4}\sum_{t=1}^{n}(1+ \lfloor \frac{n}{t} \rfloor)\times \lfloor \frac{n}{t} \rfloor \times(1+ \lfloor \frac{m}{t} \rfloor)\times \lfloor \frac{m}{t} \rfloor\sum_{d|t}\mu(\frac{t}{d})\times\frac{t^2}{d}\end{aligned}\]

\[f(t)=\sum_{t=1}^{n}(1+ \lfloor \frac{n}{t} \rfloor)\times \lfloor \frac{n}{t} \rfloor \times(1+ \lfloor \frac{m}{t} \rfloor)\times \lfloor \frac{m}{t} \rfloor\]

\[g(t)=\sum_{d|t}\mu(\frac{t}{d})\times\frac{t^2}{d}\]

那么显然,对于\(f(t)\),我们可以用数论分块做出来。

而对于\(g(t)\),由于\(\mu(\frac{t}{d})\)是积性函数,\(\frac{t^2}{d}\)是完全积性函数,所以\(g(t)\)也是积性函数。

那么对于\(g(t)\),我们在线性筛时分三种情况讨论:

  1. \(t=p\),其中\(p\)为质数,那么我们再看回这个柿子:

    \[g(t)=\sum_{d|t}\mu(\frac{t}{d})\times\frac{t^2}{d}\]

    明显,由于\(\mu\)的定义,所以当且仅当\(\frac{t}{d}=1\)\(\frac{t}{d}=p\)时才能产生贡献,使\(\mu(\frac{t}{d})\ne0\)

    \(\frac{t}{d}=1\),则\(t=d=p\)

    \[\mu(\frac{t}{d})\times\frac{t^2}{d}=\mu(1)\times\frac{p^2}{p}=p\]

    \(\frac{t}{d}=p\),又\(t=p\),则\(d=1\)

    \[\mu(\frac{t}{d})\times\frac{t^2}{d}=\mu(p)\times\frac{p^2}{1}=-p^2\]

    合并起来,即为

    \[g(t)=\sum_{d|t}\mu(\frac{t}{d})\times\frac{t^2}{d}=p-p^2\]

  2. \(t=i*p\),其中\(p\)为质数,\(i\ne1\)\(i\%p \ne 0\),即\(gcd(i,p)=1\)。那么\(g(t)=g(i)\times g(p)\)

  3. \(t=i*p\),其中\(p\)为质数,\(i\ne1\)\(i\%p = 0\),即\(gcd(i,p)=p\),不妨设\(i=t\times p^k\)

    考虑推出:

    \[g(p^k)=\sum_{d|{p^k}}\mu(\frac{p^k}{d})\times\frac{p^{2k}}{d}\]

    根据\(\mu\)的定义,当且仅当\(\frac{p^k}{d}=1\)\(\frac{p^k}{d}=p\)时才能产生贡献,使\(\mu(\frac{p^k}{d})\ne0\)

    分情况讨论解得:

    \[ \begin{aligned} g(p^k) & =\sum_{d|{p^k}}\mu(\frac{p^k}{d})\times\frac{p^{2k}}{d}\\ & =\mu(\frac{p^k}{p^k})\times \frac{p^{2k}}{p^k}+\mu(\frac{p^k}{p^{k-1}})\times\frac{p^{2k}}{p^{k-1}}\\ & =p^k-p^{k+1} \end{aligned} \]

    同理,我们可以推得:

    \[g(p^{k+1})=p^{k+1}-p^{k+2}\]

    由上述2式可得:

    \[g(p^{k+1})=g(p^k)\times p \tag{2}\]

    \[ \begin{aligned} g(t) & =g(i\times p)\\ & =g(t\times p^k \times p)\\ & =g(t)\times g(p^{k+1})\text{($t$、$p$互质)}\\ & =g(t)\times g(p^k)\times p\text{(结论(2))}\\ & =g(t\times p^k)\times p\text{($t$、$p$互质)}\\ & =g(i)\times p \end{aligned} \]

那么我们可以分3种情况讨论,线性求出每一个\(g(t)\),再维护一下\(g(t)\)的前缀和就好了。

最后的代码如下:

#include<bits/stdc++.h>

#define n 10000010
#define ll long long
#define mod 100000009

using namespace std;

int t,n,m,cnt;
ll prime[n],g[n],sum[n];
bool notprime[n];

void work()
{
    int maxn=n-10;
    g[1]=1;//记得初始化
    for(int i=2;i<=maxn;i++)
    {
        if(!notprime[i])
        {
            prime[++cnt]=i;
            g[i]=((i-1ll*i*i)%mod+mod)%mod;//第一种情况:t=p
        }
        for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++)
        {
            notprime[i*prime[j]]=true;
            if(!(i%prime[j]))
            {
                g[i*prime[j]]=g[i]*prime[j]%mod;//第二种情况:t=i%p且i%p=0
                break;
            }
            g[i*prime[j]]=g[i]*g[prime[j]]%mod;//第三种情况:t=i%p且i%p!=0
        }
    }
    for(int i=1;i<=maxn;i++)
        sum[i]=(sum[i-1]+g[i])%mod;//维护前缀和
}

ll query(int n,int m)
{
    ll ans=0;
    for(int l=1,r=0;l<=n;l=r+1)//数论分块
    {
        r=min(n/(n/l),m/(m/l));
        ll x=n/l,y=m/l;
        ans=(ans+(((1ll+x)*x/2ll%mod)*((1ll+y)*y/2%mod)%mod)*(sum[r]-sum[l-1])%mod)%mod;
    }
    return ans;
}

int main()
{
    work();//线性筛
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        printf("%lld\n",(query(n,m)%mod+mod)%mod);
    }
    return 0;
}