暴力出七级

· · 题解

PCOPTRIP。

\begin{aligned} \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} [(i,j) = 1][(j,k) = 1][(i,k) = 1] \\ = \sum_{i=1}^{n} \sum_{(i,j) = 1} \sum_{(i,k) = 1} [(j,k) = 1] \\ = \sum_{i=1}^{n} \sum_{(i,j) = 1} \sum_{(i,k) = 1} \sum_{d \mid j, d \mid k} \mu(d) \\ = \sum_{i=1}^{n} \sum_{(d,i) = 1} \mu(d) \sum_{j=1}^{\lfloor \dfrac{n}{d} \rfloor}[(i,j) = 1] \sum_{k=1}^{\lfloor \dfrac{n}{d} \rfloor} [(i,k) = 1]\\ = \sum_{i=1}^n \sum_{d=1}^{n}[(i,d) = 1] \mu (d) (\sum_{j=1}^{\lfloor \dfrac{n}{d} \rfloor}[(i,j) = 1])^2 \end{aligned}

设 \begin{aligned} F(n,i) = \sum_{d=1}^{n} [(d,i) = 1] \mu(d) \end{aligned}，\begin{aligned} G(n,i) = \sum_{d=1}^{n} [(d,i) = 1] \end{aligned}，如果枚举 i 再对 d 整除分块，设整除分块右端点集合是 \{r_1,r_2, \dotsb , r_k\}，则

= \sum_{i=1}^{n} \sum_{id=1}^{k} (F(r_{id},i)-F(r_{id-1},i)) \times G^2(\lfloor \dfrac{n}{r_{id}} \rfloor,i)

注意到集合 \{r\} 是确定的，那么集合 \{\lfloor \dfrac{n}{r} \rfloor\} 也是确定的，考虑直接预处理每个取值处的每个 i 的函数值：

对于 F：

F(n,i) = \sum_{d=1}^{n} \mu(d) \sum_{d_1 \mid d, d_1 \mid i} \mu(d_1) = \sum_{d_1 \mid i} \mu(d_1) \sum_{d_1 \mid d, d \le n} \mu(d)

枚举 j = 1 \sim k，考虑先对 x = 1 \sim r_j 预处理出 f(x) = \sum_{x \mid y , y \le r_{j}} \mu(y)，这个直接暴力即可做到调和级数 O(r_j \ln r_j)；然后枚举 x = 1 \sim r_j 对每个 i = kx 的 F(i) 加上 \mu(x) \times f(x)，因为你要对 i = 1 \sim n 处理，所以这部分是 O(\sum_{i=1}^{r_j}\lfloor \dfrac{n}{i} \rfloor)，所以对每个 r_j 都做一次复杂度就是 O(\sum_{j=1}^{k} r_j \ln r_j + \sum_{i=1}^{r_j}\lfloor \dfrac{n}{i} \rfloor)，看起来是 O(n \sqrt{n} \ln n)，算下来是 6011404 + 399635077= 405646481，我知道你看了这个很急，但是你先别急。

对于 G：

G(n,i) = \sum_{d=1}^{n}[(d,i) = 1] = \sum_{d=1}^{n} \sum_{d_1 \mid i, d_1 \mid d} \mu(d_1) = \sum_{d_1 \mid i} \lfloor \dfrac{n}{d_1} \rfloor \mu(d_1)

同理是 O(\sum_{i=1}^{\lfloor \frac{n}{r_{j}} \rfloor} \lfloor \dfrac{n}{i} \rfloor)，跟上面那个一样。

然后再做一次 O(n \sqrt{n}) 的计算就行了，这部分其实比上面的小多了。

因为我们的预处理是直接对每个 i 都求一遍，所以可以同时算答案。这样只需要开 i 这维的数组，空间是 O(n)。

你会发现我们算下来貌似要跑很久，但是甚至不需要精细实现，2.8s 就飞过去了。 

Sieve(100000); int T;
for(cin>>T;T--;){
    cin>>n; ll res = 0;
    for(int l=1,r;l<=n;l=r=r+1){
        int LIM = n/l; r = n/LIM;
        for(int x=1;x<=r;++x) for(int y=x;y<=r;y+=x) f[x] += mu[y];
        for(int x=1;x<=r;++x){ ll d = 1ll*mu[x]*f[x]; for(int y=x;y<=n;y+=x) F[y] += d; }
        for(int x=1;x<=LIM;++x){ ll d = 1ll*mu[x]*(LIM/x); for(int y=x;y<=n;y+=x) G[y] += d; }
        for(int i=1;i<=n;++i) res += 1ll*G[i]*G[i]*(F[i]-lstF[i]);
        copy(F+1,F+n+1,lstF+1), fill(F+1,F+n+1,0), fill(G+1,G+n+1,0), fill(f+1,f+r+1,0);
    }
    fill(lstF+1,lstF+n+1,0), cout<<res<<'\n';
}

能做到 O(n \sqrt{n}) 的方法有两种，一种要建图，另一种是 dp。接下来介绍第二种方法（参考题解），对于第一种，可以去看另一篇题解。

如果我们只对 i = \prod p_j 求 F(n,i)（也就是说，i 事实上是一个质因子集合），那么可以得到

F(n,i) = F(n,\dfrac{i}{p_i}) + F(\lfloor \dfrac{n}{p_i} \rfloor , i)

其中 p_i 表示 i 的最小质因子。对于存在质因子次数 \ge 2 的 i，我们可以分解质因子后直接利用这个值。

（第一项放宽了对于 p_i 的限制；对于第二项，由于 \mu(x) 只在 x = \prod p_j 处有值，所以只考虑 p_i 的次数为 1 的情况，对于 [1,\lfloor \dfrac{n}{p_i} \rfloor] 中每个与 i 互质的数，都乘上一个 p_i，那么 \mu(p_i x) = -\mu(x)，这一项本来应该减去，所以系数为 1。）

类似地可以写出 G 的转移：

G(n,i) = G(n,\dfrac{i}{p_i}) - G(\lfloor \dfrac{n}{p_i} \rfloor, \dfrac{i}{p_i})

这个东西对于一个固定的 n，对每个 i 算一遍就是 O(n) 的（递推），那么对 \{r\} 和 \{\lfloor \dfrac{n}{r} \rfloor\} 算一遍就是 O(n \sqrt{n}) 的了。

代码其实很好写，可以事先把每个数组对应的式子写出来，避免混淆。

这里放个正解的完整版代码。 

#include <bits/stdc++.h>
using namespace std;

#define ep emplace_back
using ll = long long;
inline ll Sqr(int x){ return 1ll*x*x; }
constexpr int N = 100003, Q = 862;
int n, Minp[N], id[N], cnt, mu[N], R[N], B[N];
int bs[N], tot, Smu[N], F[Q][N], G[Q][N];
vector<int> pr; bitset<N> vis;

inline void Prepare(int n){
    mu[1] = Smu[1] = 1;
    for(int i=1;i<=n;++i) B[i] = 1;
    for(int i=2;i<=n;++i){
        if(!vis[i]) pr.ep(i), mu[i] = -1, Minp[i] = B[i] = i;
        for(int P : pr){
            int to = i*P; if(to > n) break; vis[to] = 1;
            if(i%P == 0){ mu[to] = 0, B[to] = B[i]; break; }
            mu[to] = -mu[i], !Minp[to] && (Minp[to] = P), B[to] = B[i]*P;
        } Smu[i] = Smu[i-1] + mu[i];
    }
}
inline ll Sol(){
    for(int i=1;i<=cnt;++i)
        fill(F[i]+1,F[i]+n+1,0), fill(G[i]+1,G[i]+n+1,0);
    ll res = cnt = tot = 0;
    for(int i=1;i<=n;++i) if(B[i] == i) bs[++tot] = i;
    for(int l=1,r;l<=n;l=r+1)
        r = n/(n/l), R[id[r] = ++cnt] = r,
        F[cnt][1] = Smu[r], G[cnt][1] = r;
    for(int i=1;i<=cnt;++i){
        for(int j=2;j<=tot;++j){ // bs[1] = 1 with no Minp
            const int x = bs[j], nxt = x/Minp[x];
            F[i][x] = F[i][nxt] + F[id[R[i]/Minp[x]]][x],
            G[i][x] = G[i][nxt] - G[id[R[i]/Minp[x]]][nxt];
        }
    }
    for(int i=1;i<=cnt;++i)
        for(int x=1;x<=n;++x)
            res += Sqr(G[id[n/R[i]]][B[x]]) * (F[i][B[x]] - F[i-1][B[x]]);
    return res;
}

main(){
    ios::sync_with_stdio(0), cin.tie(0);
    Prepare(100000); int T; cin>>T;
    while(T--) cin>>n, cout<<Sol()<<'\n';
}

2.04s。可能是我的实现不够精细。