P9308 题解 / 有趣莫反题

· · 题解

提供一个 \Theta(n\log \log n) 的做法。

先把 \text{lcm} 转为 \gcd：

f(n)=\sum_{1\le i,j,k\le n}[i+j+k=n]\dfrac{i(j,k)}{(i,j,k)}

接着我们考虑消去 i：

\begin{aligned}f(n)&=\sum_{1\le j,k\le n}[j+k\le n-1]\dfrac{(n-j-k)(j,k)}{(n-j-k,j,k)}\\&=\sum_{1\le j,k\le n}[j+k\le n]\dfrac{(n-j-k)(j,k)}{(n,j,k)}\end{aligned}

枚举 d=(j,k)：

\begin{aligned}f(n)&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{1\le j,k\le n}[(j,k)=d][j+k\le n](n-j-k)\\&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{1\le j,k\le \frac nd}[(j,k)=1]\left[j+k\le \frac nd\right](n-dj-dk)\end{aligned}

枚举 s=j+k：

\begin{aligned}f(n)&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{2\le s\le \frac nd}(n-ds)\sum_{1\le j,k\le \frac nd}[(j,k)=1][j+k=s]\\&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{2\le s\le \frac nd}(n-ds)\sum_{j\ge 1}[(j,s-j)=1]\\&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{2\le s\le \frac nd}(n-ds)\varphi(s)\end{aligned}

枚举 t=(n,d)：

&=\sum_{t|n}t\sum_{sd\le \frac nt}[s\ge 2]\left[\left(\frac nt,d\right)=1\right]d\left(\frac nt-ds\right)\varphi(s)\\ \end{aligned}

我们把内层求和设为 g(n)，即令：

g(n)=\sum_{sd\le n}[s\ge 2]\left[\left(n,d\right)=1\right]d\left(n-ds\right)\varphi(s)

可以发现我们要求的就是：

f(n)=\sum_{t|n}tg\left(\frac nt\right)=n\sum_{t|n}\frac {g(t)}{t}

下面我们看下如何快速求 g(n)。

利用莫反处理 (n,d)=1：

\begin{aligned}g(n)&=\sum _ {t|n}\mu(t)\sum_{sd\le n}[s\ge 2]\left[t|d\right]d\left(n-ds\right)\varphi(s)\\&=\sum _ {t|n}t^2\mu(t)\sum_{sd\le \frac nt}[s\ge 2]d\left(\frac nt-ds\right)\varphi(s)\end{aligned}

我们再次将内层求和设为 h(n)，即：

h(n)=\sum_{sd\le n}[s\ge 2]d\left(n-ds\right)\varphi(s)

则有：

g(n)=\sum_{t|n}t^2\mu(t)h\left(\frac nt\right)=n^2\sum_{t|n}\mu\left(\frac nt\right)\frac{h(t)}{t^2}

下面考虑 h(n) 快速求法。

先剔除 s\ge 2 这个条件：

\begin{aligned}h(n)&=\sum_{sd\le n}[s\ge 2]d\left(n-ds\right)\varphi(s)\\&=\sum_{sd\le n}d\left(n-ds\right)\varphi(s)-\sum_{d=1}^nd(n-d)\end{aligned}

接着枚举 k=sd，并设 \tau(n)=\sum_{d|n}d\varphi(\frac nd)。

\begin{aligned}h(n)&=\sum_{k=1}^n(n-k)\sum_{d|k}d\varphi\left(\frac kd\right)-\frac{n(n-1)(n+1)}{6}\\&=n\sum_{k=1}^n\tau(k)-\sum_{k=1}^nk\tau(k)-\frac{n(n-1)(n+1)}{6}\\\end{aligned}

酱紫就推完啦！

至于 \tau(n)，通过简单的推导可知：

\tau(pn)=\begin{cases}2p-1&n=1\\\tau(p)\tau(n)&p\nmid n\\ 2p\tau(n)-p^2\tau(n/p)& p\mid n\end{cases}

可以线性筛。

我们总结一下步骤：

  1. 线性递推求逆元；

  2. 线性筛出 \tau(1),\tau(2),\cdots,\tau(n) 的值；

  3. 求出 h(1),h(2),\cdots,h(n) 的值。

  4. 对 h(n)/n^2 做 Dirichlet 差分，得到 g(1)/1^2,\cdots,g(n)/n^2；

  5. 对 g(n)/n 做 Dirichlet 前缀和，即得 f(1)/1,\cdots,f(n)/n。

总时间复杂度是 \Theta(n\log \log n)，目前为最优解。

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int Mx = 1e6 + 100, Mod = 998244353;

bool Vis[Mx];
int Tau[Mx], Prime[Mx], tot;
int Inv[Mx];

void Sieve(){
    Tau[1] = 1;
    for(int i = 2; i < Mx; ++i){
        if(!Vis[i]) Prime[++tot] = i, Tau[i] = 2 * i - 1;
        for(int j = 1; j <= tot && Prime[j] * i < Mx; ++j){
            Vis[i * Prime[j]] = true;
            if(i % Prime[j] == 0){
                Tau[i * Prime[j]] = Prime[j] * (2 * Tau[i] - Prime[j] * Tau[i / Prime[j]]);
                break;
            }
            Tau[i * Prime[j]] = Tau[i] * Tau[Prime[j]];
        }
    }
}

void GetInv(){
    Inv[1] = 1;
    for(int i = 2; i < Mx; i++) Inv[i] = -1ll * Inv[Mod % i] * (Mod / i) % Mod;
}

int H[Mx];
int main(){
    Sieve(), GetInv();
    int n; cin >> n;
    int H0 = 0, H1 = 0;
    for(int i = 1; i <= n; ++i){
        H0 = (H0 + Tau[i]) % Mod;
        H1 = (H1 + 1ll * i * Tau[i]) % Mod;
        H[i] = (H0 - 1ll * Inv[i] * H1 - (i - 1ll) * (i + 1ll) % Mod * Inv[6]) % Mod * Inv[i] % Mod;
    }
    for(int i = 1; Prime[i] <= n; ++i){
        for(int j = n / Prime[i]; j; --j){
            H[j * Prime[i]] = (H[j * Prime[i]] - H[j]) % Mod;
        }
    }
    for(int i = 1; i <= n; ++i) H[i] = 1ll * i * H[i] % Mod;
    for(int i = 1; Prime[i] <= n; ++i){
        for(int j = 1; j * Prime[i] <= n; ++j){
            H[j * Prime[i]] = (H[j * Prime[i]] + H[j]) % Mod;
        }
    }
    for(int i = 1; i <= n; ++i){
        int Ans = 1ll * H[i] * i % Mod;
        if(Ans < 0) Ans += Mod;
        printf("%d ", Ans);
    }
    return 0;
}