Solution - Atcoder Xmas2019D Sum of (-1)^f(n).md

对于 \(f(i) = (-1)^{\sum\limits_j c_j}(i = \prod\limits_j p_j^{c_j}(p_j\in \mathbb{P}))\)，一个比较特殊的值就是在 \(i\in \mathbb{P}\) 时有 \(f(i) = -1\)。
于是考虑 Powerful Number 筛，构造积性函数 \(g\) 使得对于 \(i\in \mathbb{P}\) 有 \(g(p) = f(p)\) 且 \(g\) 易前缀求和。
那么就可以考虑构造 \(g = \mu\)。

接下来考虑得到 \(h = f / g\)。
那么能够发现因为有 \(f(1) = g(1) = h(1) = 1, f(i) = g(i) = -1(i\in \mathbb{P})\)，于是可以知道 \(h(i) = 0(i\in \mathbb{P})\)。
又因为 \(h = f / g\) 也是一个积性函数，若对于 \(i = \prod\limits_j p_j^{c_j}(p_j\in \mathbb{P})\) 存在 \(c_j = 1\)，那么有 \(h(i) = 0\)。
于是可以知道满足 \(h(i)\not = 0\) 的 \(i\) 可以表示为 \(a^2 b^3\) 的形式，通过积分可以知道对应的数量是 \(\mathcal{O}(\sqrt{n})\) 级别的。

然后来考虑求解 \(F(n) = \sum\limits_{i = 1}^n = f(i)\)。
就有 \(F(n) = \sum\limits_{i = 1}^n f(i) = \sum\limits_{i = 1}^n \sum\limits_{j | i} h(j)g(\frac{i}{j}) = \sum\limits_{j = 1}^n \sum\limits_{j | i, i\le n} h(j) g(\frac{i}{j}) = \sum\limits_{j = 1}^n h(j)G(\lfloor\frac{n}{j}\rfloor)\)，其中 \(G(n) = \sum\limits_{i = 1}^n g(i)\)。
因为上文说到了 \(h(j)\not = 0\) 的数量是 \(O(\sqrt{n})\) 级别的，所以这部分的复杂度无需在意，直接搜索 \(h(j)\not = 0\) 的 \(j\) 即可。
于是重点到了求 \(G(\lfloor\frac{n}{x}\rfloor)\)，因为 \(g = \mu\)，所以只需要实现求 \(\lfloor\frac{n}{x}\rfloor\) 位置的 \(\mu\) 的前缀和，用杜教筛就可以了。

时间复杂度 \(\mathcal{O}(n^{\frac{2}{3}})\)。

#include<bits/stdc++.h>
using ll = long long;
using i128 = __int128_t;
const ll limn = 1e12, limB1 = (ll)pow(limn, 2.0 / 3), limB2 = (ll)pow(limn, 1.0 / 2);
ll n, B1, B2;
int pr[limB1 + 1], mn[limB1 + 1], m;
int mu[limB1 + 1]; ll sum1[limB1 + 1];
int leq[limB2 + 1], geq[limB2 + 1], tot;
ll val[limB2 * 2 + 1], sum[limB2 * 2 + 1];
inline int &id(ll x) {return x <= B2 ? leq[x] : geq[n / x];}
ll h[80];
ll dfs(int w, ll x, ll H) {
   if (! H)
      return 0;
   if (w > m || (i128)x * pr[w] > n || (i128)x * pr[w] * pr[w] > n)
      return H * sum[id(n / x)];
   ll ans = 0;
   for (int i = 0; x <= n; x *= pr[w], i++)
      ans += dfs(w + 1, x, H * h[i]);
   return ans;
}
int main() {
   scanf("%lld", &n), B1 = std::max(1ll, (ll)pow(n, 2.0 / 3)), B2 = (ll)pow(n, 1.0 / 2);
   mu[1] = 1ll;
   for (int i = 2; i <= B1; i++) {
      if (! mn[i])
         mn[i] = i, mu[i] = -1, pr[++m] = i;
      for (int j = 1; i * pr[j] <= B1 && j <= m; j++) {
         mu[i * pr[j]] = mn[i] == pr[j] ? 0ll : -mu[i], mn[i * pr[j]] = pr[j];
         if (mn[i] == pr[j])
            break;
      }
   }
   for (int i = 1; i <= B1; i++)
      sum1[i] = sum1[i - 1] + mu[i];
   for (ll l = 1, r = 0; l <= n; l = r + 1) {
      r = n / (n / l);
      val[id(n / l) = ++tot] = n / l;
   }
   for (int i = tot; i; i--) {
      ll x = val[i];
      if (x <= B1) {
         sum[i] = sum1[x];
         continue;
      }
      sum[i] = 1ll;
      for (ll l = 1, r = 0; l < x; l = r + 1) {
         r = std::min(x / (x / l), x - 1);
         sum[i] -= sum[id(x / l)] * (r - l + 1);
      }
   }
   h[0] = 1ll;
   for (ll i = 1, x = 2ll, f = -1; x <= n; i++, x <<= 1, f = -f)
      h[i] = f + h[i - 1];
   while (pr[m] > B2) m--;
   printf("%lld\n", dfs(1, 1ll, 1ll));
   return 0;
}