LCM 求和问题的新优选！

tzhengqing · 2026-10-08 10:03:47 · 算法·理论

好像也并没有很优

前言

本文将给出积性函数 h 满足 \sum\limits_{d|n}h(d)=\frac{1}{n} 和拓展 \sum\limits_{d|n}h_k(d)=\frac{1}{n^k}，
将 \gcd 代入 n 即可得到 LCM 求和问题较为简单的做法。
注意 h 函数的用处一般在于简化推导而不是降低复杂度。

本文有时会使用 n/d 来表示 \lfloor\frac{n}{d}\rfloor，这样比较方便且简明。

引入

我们在爆杀莫反题的时候有可能会遇到诸如 \frac{1}{\gcd(i,j)} 的式子，
一般情况下我们会使用钦定法，再把单位函数拆为莫反，交换求和解决问题。
例如求 \sum\limits_{i=1}^{n}\operatorname{lcm}(i,n)： :::error[石山步骤]

::: 虽然这样做出来了，但是推起来太麻烦了！这还只是最基础的 LCM 求和而已。
发现问题出在 \gcd 在分母不能直接加减，我们想到，如果构造函数（夹带私货地，不妨称为 h），使得

那我们就可以避免除法直接交换顺序求和了！

研究

积性

由定义式，反演得到

那这个一眼积性函数了，性质多多的。
注意其取值范围为 \R，需要模数为质数且大于 n 才能用。

质数幂

考察 \sum\limits_{d|n}d\mu(d) 在 1,p,p^2,...,p^x 的取值分别为 1,-p,0,...,0，可以得到

欧拉筛

上式可以简单做欧拉筛，对于 x \geq 2 有

写成代码就是 h[d]=h[i]*qpow(pr[j],p-2)%p，也是非常的简单。
这里贴出一份 O(n \log n) 的完整代码。 :::success[Code]

#define int long long
const int N=1145141,p=998244353;//可修改的参数
int h[N],cnt=0,pr[N],isp[N];
inline int qpow(int a,int b)
{
    int x=1,y=a;
    while(b)
    {
        if(b&1)x=x*y%p;
        y=y*y%p;
        b>>=1;
    }
    return x;
}
void init()
{
    h[1]=1;
    for(int i=2; i<N; i++)
    {
        if(!isp[i])
        {
            pr[++cnt]=i;
            h[i]=qpow(i,p-2)-1;
        }
        for(int j=1; j<=cnt&&i*pr[j]<N; j++)
        {
            int d=i*pr[j];
            isp[d]=1;
            if(i%pr[j]==0)
            {
                h[d]=h[i]*qpow(pr[j],p-2)%p;
                break;
            }
            h[d]=h[i]*h[pr[j]]%p;
        }
    }
}

:::info[Solution] 直接上 h 函数，看看优化效果：

轻松秒杀。记忆化一下，均摊时间复杂度 O(\log n)。

不是怎么没有模数？？直接只剩理论价值了。模数的性质要比较优秀才能使用 h 函数。
主包尝试在这里取 p=100000000010299 再使用 __int128，卡了三发评测，对不起。/ll ::: 例题 2：求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\operatorname{lcm}(i,j)。

:::info[Solution] 这题也是拉完了，建议降绿好吧。直接上 h 函数：（设 n<m）

这不秒了吗。虽然本来也不难。
这个做法的好处是形式上也相当简单，不用做整除分块了。
如果带整除分块还可以开多测，时间复杂度 O(n+T\sqrt{n})。

随手贴一个代码吧，虽然实现有点劣。跑了大概 600ms。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=10000005,p=20101009;
int h[N],cnt=0,pr[N],isp[N];
inline int qpow(int a,int b)
{
    int x=1,y=a;
    while(b)
    {
        if(b&1)x=x*y%p;
        y=y*y%p;
        b>>=1;
    }
    return x;
}
void init()
{
    h[1]=1;
    for(int i=2; i<N; i++)
    {
        if(!isp[i])
        {
            pr[++cnt]=i;
            h[i]=qpow(i,p-2)-1;
        }
        for(int j=1; j<=cnt&&i*pr[j]<N; j++)
        {
            int d=i*pr[j];
            isp[d]=1;
            if(i%pr[j]==0)
            {
                h[d]=h[i]*qpow(pr[j],p-2)%p;
                break;
            }
            h[d]=h[i]*h[pr[j]]%p;
        }
    }
}
int S(int x){return x*(x+1)/2%p;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,ans=0;cin>>n>>m;
    init();if(n>m)swap(n,m);
    for(int i=1;i<=n;i++)ans=(ans+i*i%p*h[i]%p*S(n/i)%p*S(m/i))%p;
    cout<<ans;
    return 0;
}

:::

进阶

例题 3：求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=0}^{m}\operatorname{lcm}^k(i,j)。

:::info[Solution] 利用 h_k，枚举 k，对于单个的 k，可以得到

其中 P_k(x)=\sum\limits_{i=1}^{x}i^k，这个筛好 i^k 之后直接算就行。
对于所有的 k，总时间复杂度 O(nm)。 :::

提高

例题 4：求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{a=0}^{m}\sum\limits_{b=0}^{k}\frac{\operatorname{lcm}^a(i,j)}{\gcd^b(i,j)}。

:::info[Solution] 例题 3 的略微加强版。

例题 5：多组询问求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}\operatorname{lcm}(i,j,k)\times i^i \times j^j \times k^k。

:::info[Solution] 记答案为 Ans(n)。

观察到这个东西可以做增量。
具体地，假如你已经知道了 Ans(n-1) 的值，你就可以钦定 i,j,k 中的几个是 n。
对着这个东西做容斥是方便的。

复杂度瓶颈显然是求 g(n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\operatorname{lcm}(n,i,j)i^ij^j。

三元 \operatorname{lcm} 太讨厌了，必须拆开，注意到：

证明显然，分别考虑每个质因子即可。
考虑令 f_n(x)=x^x\frac{x}{\gcd(n,x)}，则

于是可以得到

交换求和顺序，记 w=\operatorname{lcm}(d,e)：

这里考虑令 F_n(x)=\sum\limits_{i=1}^{n/x}f_n(ix)，显然这个东西可以 O(n \log n) 预处理，代入得到

于是直接计算，总时间复杂度为 O(n^2 \log n)。
对每个 d 预处理所有 \operatorname{lcm}(d,e) 再排序遍历可以做到 O(n^2)，实测速度几乎没区别。 ::: 欢迎大家探索更多的妙妙用法。真的会有吗

总结