洛谷 P1829 [国家集训队]Crash的数字表格 / JZPTAB（莫比乌斯反演）

题意：求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$。

开始开心（自闭）化简：

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

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

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

=$\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\mu(i)i^2S({\lfloor \frac{n}{id}\rfloor})S({\lfloor \frac{m}{id}\rfloor}),S(n)=(n+1)*n/2$

=$\sum_{T=1}^{n}S({\lfloor \frac{n}{T}\rfloor})S({\lfloor \frac{m}{T}\rfloor})\sum_{d|T}d(\frac{T}{d})^2\mu(\frac{T}{d})$

=$\sum_{T=1}^{n}S({\lfloor \frac{n}{T}\rfloor})S({\lfloor \frac{m}{T}\rfloor})T\sum_{d|T}(\frac{T}{d})\mu(\frac{T}{d})$

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

只需要预处理F的前缀和，前面整除分块问题就解决了。

$F(1)=1，F(p^c)=\mu(1)*1+\mu(p)*p=1-p$

可以知道F是一个积性函数，对T进行质因数分解，即可求得F(T)，可以在筛质数的时候进行求解，具体看代码。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e7+;

const int MD=;

bool p[N];

int pri[N],f[N],tot;

void init() {

    f[]=;

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

        if(!p[i]) pri[tot++]=i,f[i]=-i+MD;

        for(int j=;j<tot&&i*pri[j]<N;j++) {

            p[i*pri[j]]=true;

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

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

                break;

            }

            else f[i*pri[j]]=1LL*f[i]*f[pri[j]]%MD;

        }

    }

    for(int i=;i<N;i++) f[i]=1LL*f[i]*i%MD;

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

}

int cal(int x) {

    return 1LL*x*(x+)/%MD;

}

int main() {

    init();

    int n,m;

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

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

    int ans=;

    for(int l=,r;l<=n;l=r+) {

        r=min(n/(n/l),m/(m/l));

        ans=(ans+1LL*(f[r]-f[l-]+MD)*cal(n/l)%MD*cal(m/l)%MD)%MD;

    }

    printf("%d\n",ans);

    return ;

}

巴特西

洛谷 P1829 [国家集训队]Crash的数字表格 / JZPTAB（莫比乌斯反演）

最新文章

热门文章