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

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

首先呢……\(\mu(x^2)\)是忽悠你玩的，这个东西只在\(x = 1\)时取到\(1\)，其他情况下都是\(0\)。

然后\(\varphi(x^2)\)好难哎……不过我们可以证明它是积性函数，证明的话考虑两个满足\(x\perp y\)（那么很显然也有\(x^2\perp y^2\)）的正整数，有：

\[\varphi((xy)^2)=\varphi(x^2y^2)=\varphi(x^2)\varphi(y^2)\]

用贝尔级数啊，三回啊三回（屑颜）

那么考虑推\(\varphi(x^2)\)（直接设成\(f\)吧）的生成函数：

\[
\begin{aligned}
f_p(x)&=1 + p(p - 1)x + p^3(p - 1)x^2 + \ldots\\
&= 1 + p(p - 1)x(1 + p^2x + p^4x^2 + \ldots)\\
&= 1 + \frac{p^2x - px}{1 - p^2x}\\
&= \frac{1 - px}{1 - p^2x}
\end{aligned}
\]

这个可以有啊（赞赏）

那么我们知道\(\mathrm{id}_p(x) = \frac{1}{1 - px}\)，由此可得\((f\ast \mathrm{id})_p(x) = \frac{1}{1 - p^2x}\)，因此有\((f\ast \mathrm{id}) = \mathrm{id}^2\)。一次和二次的等幂求和的式子都很简单，所以直接杜教筛即可。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long ll;
const ll ha = 1000000007LL;
const int N = 10000000;
int prm[N + 5]; bool vis[N + 5];
ll phi2[N + 5], S[N + 5];
inline void process() {
  vis[N] = true; phi2[1] = 1; int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      phi2[i] = (ll)i * (ll(i - 1)) % ha;
      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) {
        phi2[v] = phi2[i] * ((ll)prm[j] * (ll)prm[j] % ha) % ha; break;
      } else {
        phi2[v] = phi2[i] * phi2[prm[j]] % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    S[i] = (S[i - 1] + phi2[i]) % ha;
  }
}

inline ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
inline ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

inline ll H1(ll n) {
  static const ll inv_2 = inv(2);
  ll ret = n * (n + 1LL) % ha;
  ret = ret * inv_2 % ha;
  return ret;
}
inline ll H2(ll n) {
  static const ll inv_6 = inv(6);
  ll ret = n * (n + 1LL) % ha;
  ret = ret * (n * 2LL + 1LL) % ha;
  ret = ret * inv_6 % ha;
  return ret;
}
__gnu_pbds::gp_hash_table<int, ll> p2;
ll phi2_S(int n) {
  if(n <= N) return S[n];
  if(p2.find(n) != p2.end()) return p2[n];
  ll ret = H2(n);
  ll las = 1;
  for(int i = 2; i <= n;) {
    int next = n / (n / i);
    ll nv = H1(next);
    ll th = (nv - las + ha) % ha;
    ret = (ret - th * phi2_S(n / i) % ha + ha) % ha;
    i = next + 1; las = nv;
  }
  p2[n] = ret;
  return ret;
}

int main() {
  process();
  int n; scanf("%d", &n);
  printf("1\n%lld\n", phi2_S(n));
  return 0;
}

• 相关文章
• 全局相关文章