设 \(\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\}\)，则
注意到集合 \(\{r\}\) 是确定的，那么集合 \(\{\lfloor \dfrac{n}{r} \rfloor\}\) 也是确定的，考虑直接预处理每个取值处的每个 \(i\) 的函数值：
对于 \(F\)：
枚举 \(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)\)，这个也是暴力就可以 \(O(r_j \ln r_j)\) 的 因为你要对 \(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\)，我觉得它应该能过把（/ng
对于 \(G\)：
同理是 \(O(\sum_{i=1}^{\lfloor \dfrac{n}{r_{j}} \rfloor} \lfloor \dfrac{n}{i} \rfloor)\)，跟上面那个一样。
然后再做一次 \(O(n \sqrt{n})\) 的计算就行了（，这部分就比上面的小多了。
其实因为预处理的时候直接对每个 \(i\) 都求答案了，所以不如直接同时算答案，这样数组也只需要开一个，空间是 \(O(n)\)（
那这样算上常数我也不知道 \(20s\) 能不能过（
怎么 2.8s 就飞过去了 /ng。
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\) 事实上是一个质因子集合），那么可以得到
其中 \(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\) 的转移：
这个东西对于一个固定的 \(n\)，对每个 \(i\) 算一遍就是 \(O(n)\) 的（递推），那么对 \(\{r\}\) 和 \(\{\lfloor \dfrac{n}{r} \rfloor\}\) 算一遍就是 \(O(n \sqrt{n})\) 的了。
这里写线筛就没有必要了，埃筛应该会好写很多。我错了 /ll。
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;
}
2.04s，差点没暴力跑得快（