[BZOJ 4916]神犇与蒟蒻

danihao123 posted @ 2018年9月12日 20:16 in 题解 with tags BZOJ 狄利克雷卷积 贝尔级数 杜教筛 , 9 阅读
转载请注明出处:http://danihao123.is-programmer.com/

给定\(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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter