danihao123's Blog

给定\(n\)，分别求出\(\mu(x^2)\)和\(\varphi(x^2)\)的前\(n\)项和。

\(1\leq n\leq 10^9\)。

沿用约数个数和一题的思路……可以列出此式：

\[\sigma_1(ij) = \sum_{a | i}\sum_{b | j} ab[\gcd(\frac{i}{a}, b) = 1]\]

然后我们考虑去化简原式：

\[
\begin{aligned}
\sum_{i = 1}^n\sum_{j = 1}^n\sum_{a | i}\sum_{b | j} ab\sum_{d | \frac{i}{a}, d | j}\mu(d)
\end{aligned}
\]

接下来我们考虑枚举\(d\)，但是\(a\)和\(b\)的贡献又有点麻烦了……

\(b\)的贡献还好说，直接枚举\(b\)本身是\(d\)的多少倍就是\(\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\)。那\(a\)的贡献如何考虑？

我们考虑直接去枚举\(a\)本身……可以注意到一定有\(a\le\lfloor\frac{n}{d}\rfloor\)（因为\(\frac{i}{a}\ge d\)），所以直接枚举\(a\)本身之后再考虑\(\lfloor\frac{n}{a}\rfloor\)范围内\(d\)的倍数的数量即可（相当于找\(\frac{i}{a}\)），因此贡献为\(\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\)。

那么继续化简原式：

\[
\begin{aligned}
\quad&\sum_{d = 1}^n\mu(d)\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\\
=&\sum_{d = 1}^n\mu(d)d(\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} i\lfloor\frac{n}{id}\rfloor)^2\\
=&\sum_{d = 1}^n\mu(d)d S_1^2(\lfloor\frac{n}{d}\rfloor)
\end{aligned}
\]

此处\(S_1\)表示\(\sigma_1\)的前缀和。

接下来预处理\(\mu(d)d\)的前缀和，考虑杜教筛。我们发现该函数和\(\mathrm{id}\)卷出来就是\(\epsilon\)（证明可以考虑贝尔级数……这种方式非常有效，并且还能帮我们找到需要卷的函数，我有时间会专门撰文写一下），所以杜教筛一波即可。这部分总复杂度为\(O(n^{\frac{2}{3}})\)。

至于\(S_1\)，我们考虑不大于\(n^{\frac{2}{3}}\)可以直接预处理，剩下的用时就用\(O(\sqrt{n})\)的方法求（考虑到反演不会用到\(S_1\)的重复状态所以不需要记忆化）。用类似于杜教筛复杂度证明的方法可以证明该部分总复杂度为\(O(n^{\frac{2}{3}})\)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
const int N = 1000000;
using ll = long long;
const ll ha = 1000000007LL;
const ll i2 = 500000004LL;
ll mud[N + 5], sig_1[N + 5];
int prm[N + 5]; bool vis[N + 5];
void sieve() {
  int cnt = 0;
  mud[1] = 1;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      mud[i] = (ha - i);
      prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        mud[v] = 0; break;
      } else {
        mud[v] = (mud[i] * mud[prm[j]]) % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    for(int j = i; j <= N; j += i) {
      sig_1[j] = (sig_1[j] + (ll(i))) % ha;
    }
  }
  for(int i = 1; i <= N; i ++) {
    mud[i] = (mud[i - 1] + mud[i]) % ha;
    sig_1[i] = (sig_1[i - 1] + sig_1[i]) % ha;
  }
}

std::unordered_map<ll, ll> ma;
ll calc_id(ll x) {
  ll v1 = x, v2 = x + 1LL;
  if(x & 1LL) {
    v2 /= 2LL;
  } else {
    v1 /= 2LL;
  }
  return ((v1 * v2) % ha);
}
ll calc_mud(ll n) {
  if(n <= (ll(N))) return mud[n];
  if(ma.count(n)) return ma[n];
  ll ans = 1, las = 1;
  for(ll i = 2; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_id(next);
    ll ns = (nv - las + ha) % ha;
    ans = (ans - (ns * calc_mud(n / i)) % ha + ha) % ha;
    las = nv; i = next + 1LL;
  }
  ma[n] = ans; return ans;
}
ll calc_s1(ll n) {
  if(n <= (ll(N))) return sig_1[n];
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_id(next);
    ll ns = (nv - las + ha) % ha;
    ans = (ans + (ns * (n / i)) % ha) % ha;
    las = nv; i = next + 1LL;
  }
  return ans;
}
ll calc(ll n) {
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_mud(next); ll ns = (nv - las + ha) % ha;
    ll pv = calc_s1(n / i); pv = (pv * pv) % ha;
    ans = (ans + (ns * pv) % ha) % ha;
    las = nv; i = next + 1LL;
  }
  return ans;
}

int main() {
  sieve();
  ll n; scanf("%lld", &n);
  printf("%lld\n", calc(n));
  return 0;
}