洛谷P1892 莫比乌斯反演，套路处理技巧

题意：

给出$n,m$，计算
$$\sum _{i=1}^n\sum _{j=1}^{m}lcm(i,j)$$

Solution：

$lcm$不好处理转化为$gcd$，有
$$\sum _{i=1}^n\sum _{j=1}^m\frac{ij}{gcd(i,j)}$$
优先枚举因子$gcd$，这样可以转化成整除问题
$$\sum _{d=1}^n\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)=d]\frac{ij}{d}$$
利用$gcd(i,j)=d\Rightarrow gcd(\frac{i}{d},\frac{j}{d})=1$，枚举右式的$\frac{i}{d},\frac{j}{d}$作为新的$i,j$
$$\sum _{d=1}^n\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]\frac{id\cdot jd}{d}=\sum _{d=1}^n\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]ijd$$
将$d$提出
$$\sum _{d=1}^{n}d\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]ij$$
莫比乌斯函数的性质${\sum }_{d|n}\mu (d)=[n=1]$，可以将布尔表达式转化为整除，于是即求
$$\sum _{d=1}^{n}d\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }ij\sum _{t|gcd(i,j)}\mu (t)$$
再次优先枚举因子$t$，此时知道因子，只需找因子的所有倍数的和，倍数有
$$t,2t,3t,....$$
那么对于$n$，小于$n$的倍数有$\lfloor \frac{n}{t}\rfloor$个，求和即为
$$t(1+2+3+...+\lfloor \frac{n}{d}\rfloor )$$
令$sum(i)=1+2+...+i=\frac{(1+i)(i)}{2}$，那么原式可以写作
$$\sum _{d=1}^{n}d\sum _t^{min\{\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor \}}{t}^2\mu (t)sum(\frac{\lfloor \frac{n}{d}\rfloor }{t})sum(\frac{\lfloor \frac{m}{d}\rfloor }{t})$$
在题目内，可以交换$n,m$，那么不妨假设$n\le m$，即求
$$\sum _{d=1}^{n}d\sum _t^{\lfloor \frac{n}{d}\rfloor }{t}^2\mu (t)sum(\lfloor \frac{n}{dt}\rfloor )sum(\lfloor \frac{m}{dt}\rfloor )$$
枚举$T=dt$，由于此时$t$是$T$的一个因子，此时枚举$d$为$T$的因子，地位相当于上式的$t$
$$\sum _{T=1}^{n}sum(\lfloor \frac{n}{T}\rfloor )sum(\lfloor \frac{m}{T}\rfloor )T\sum _{d|T}d\mu (d)$$
其中$sum(\lfloor \frac{n}{T}\rfloor )sum(\lfloor \frac{m}{T}\rfloor )$可以整除分块解决，此时的整除分块应该保证$\lfloor \frac{n}{T}\rfloor$与$\lfloor \frac{m}{T}\rfloor$都在这个范围是不变的，所以$r$端点需要两次结果取小，剩下只需要快速求得
$$f(T)=\sum _{d|T}d\mu (d)$$
一般数论函数都是积性的，所以我们考虑给一个求出来的$f(T)$的$T$添加一个质因子$p$

• 如果$T$含有$p$，由于当一个数$n$出现了质因子的平方的时候，$\mu (n)=0$，所以这个$p,T$的分解方式不能给$\mu (Tp)$带来贡献，所以$f(Tp)=f(T)$

• 如果$T$不含有$p$，由于积性函数，$f(Tp)=f(T)f(p)$

这样就可以线性筛出所有的$f(T)$，只需要对$Tf(T)$做前缀和即可

设一个质因子为$p$，由于$\mu (p)=1-1=0$，于是设定$f(p)=\mu (p)$时即筛$\mu (i)$，上述方法只是一个筛$\mu (i)$的改动版

总时间复杂度$O(n)$

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=1e7+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=20101009;

bool nt[N];
int prime[N],cnt;
ll n,m,ans,f[N],sum[N];

void make_prime()
{
    f[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!nt[i]) prime[++cnt]=i,f[i]=((1-i)%mod+mod)%mod;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            nt[i*prime[j]]=true;
            if(i%prime[j]==0) 
            {
                f[i*prime[j]]=f[i];
                break;
            }
            else f[i*prime[j]]=f[i]*f[prime[j]]%mod;
        }
    }
    for(int i=1;i<=n;i++) f[i]=(f[i-1]+1ll*i*f[i]%mod)%mod;
    for(int i=1;i<=m;i++) sum[i]=(sum[i-1]+i)%mod;
}

ll query(ll l,ll r){
    return ((f[r]-f[l-1])%mod+mod)%mod;
}

int main()
{
    cin>>n>>m;
    if(n>m) swap(n,m);
    make_prime();
    for(ll l=1,r,val;l<=n;l=r+1)
    {
        val=n/l; r=val?min(n/val,n):n;
        val=m/l; r=min(r,val?min(m/val,m):m);
        ans=(ans+sum[n/l]*sum[m/l]%mod*query(l,r)%mod)%mod;
    }
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58