danihao123's Blog

给定正整数\(n, m\)，求\(\sum_{i = 1}^n\sum_{j = 1}^m \varphi(ij)\)，膜\(10^9+7\)输出。

\(n\leq 10^5, m\leq 10^9\)。

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

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

假设每个结点都有正整数权值，那么我们定义完美平衡树：权值为\(1\)的单点树是完美平衡树；根的权值为\(w(w\geq 2)\)的话，那么它一定有\(k(2\leq k\leq w)\)个子树，每个子树要完全一致，并且每个子树的根权值都要是\(\lfloor\frac{w}{k}\rfloor\)。

给定\(N\)，计算根权值为\(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;
}

首先这个题和能量采集几乎完全一致……稍微有点反演常识的人都知道答案事\(\sum_{i = 1}^n\varphi(i)\lfloor\frac{n}{i}\rfloor^2\)，然后你需要用\(\varphi\)的前缀和，这个东西直接杜教筛搞一波就行了。这样总复杂度事\(O(n^{\frac{2}{3}})\)的，下面给出证明。

先考虑杜教筛的部分。杜教筛可以看做一个转移复杂度为\(O(\sqrt{n})\)的DP，他的状态一定是通过总的\(n\)整除一个数得到的。不大于\(n^{\frac{2}{3}}\)的状态我们都事先预处理，那么我们假设所有大于\(n^{\frac{2}{3}}\)的状态都被计算了一遍，这些状态一定事通过\(n\)整除一个不大于\(n^{\frac{1}{3}}\)的数得到的。因此复杂度为：

\[\sum_{i = 1}^{n^{\frac{1}{3}}} \sqrt{\lfloor\frac{n}{i}\rfloor}\leq \int_0^{n^{\frac{1}{3}}} \sqrt{\frac{n}{x}}\mathrm{d}x = 2n^{\frac{2}{3}} = O(n^{\frac{2}{3}})\]

至于莫比乌斯反演，不考虑杜教筛的复杂度的话就只是\(O(\sqrt{n})\)而已了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <utility>
using ll = long long;
constexpr ll ha = 1000000007LL;
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;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

const int N = 10000000;
ll phi[N + 1]; int prm[N + 1]; bool vis[N + 1];
void sieve() {
  phi[1] = 1; vis[1] = true;
  int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      phi[i] = i - 1; 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) {
        phi[v] = phi[i] * prm[j]; break;
      } else {
        phi[v] = phi[i] * phi[prm[j]];
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi[i] = (phi[i] + phi[i - 1]) % ha;
  }
}

std::unordered_map<ll, ll> ma;
const ll i2 = inv(2LL);
ll phi_sum(ll n) {
  if(n <= (ll(N))) return phi[n];
  if(ma.count(n)) return ma[n];
  ll fg = (n % ha) * ((n + 1LL) % ha) % ha * i2 % ha;
  for(ll i = 2; i <= n;) {
    ll next = n / (n / i);
    ll len = (next - i + 1LL) % ha;
    fg = (fg - (len * phi_sum(n / i)) % ha + ha) % ha;
    i = next + 1LL;
  }
  ma[n] = fg; return fg;
}
ll calc(ll n) {
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll b = ((n / i) % ha) * ((n / i) % ha) % ha;
    ll ns = phi_sum(next);
    ans = (ans + (((ns - las + ha) % ha) * b % ha)) % ha; las = ns;
    i = next + 1LL;
  }
  return ans;
}

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

杜教筛模板题……（然而常数卡卡卡）

我还是讲一讲基础的东西吧……

先考虑求欧拉函数的前缀和，我们先找一个它的卷积（这里用\(f=\varphi\ast 1\)，且设\(g = 1\)），发现有（用\(S\)表示原函数的前缀和）：

\[\sum_{i = 1}^n f(i) = \sum_{i = 1}^n g(i)\times S(\lfloor\frac{n}{i}\rfloor) = \frac{n(n + 1)}{2}\]

第二个和式的第一项是\(g(1)\times S(n) = S(n)\)，也就是我们需要的答案。这样的话我们把第一项分割出来，后面的项大力求，然后用\(\frac{n(n + 1)}{2}\)减去那些项就得到了第一项。并且注意到\(\lfloor\frac{n}{i}\rfloor\)的取值种类是\(\sqrt{n}\)级别的，又可以大力优化一波。然后考虑预处理\(O(n^{\frac{2}{3}})\)级别的前缀和（时间和空间都允许），再优化一波。然后考虑把没预处理的状态扔一个哈希表里（反正看起来不会很多），又优化一波……

这样复杂度就是\(O(n^{\frac{2}{3}})\)的了……（又不会证了）

求莫比乌斯函数的前缀和的方法类似（并且更简单一点）……

代码（又被卡成苟了）：

/**************************************************************
	Problem: 3944
	User: danihao123
	Language: C++
	Result: Accepted
	Time:11292 ms
	Memory:127740 kb
****************************************************************/

#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 int N = 3500000;
const int maxn = N + 5;
ll phi[maxn], phi_S[maxn];
ll mu[maxn], mu_S[maxn];
void sieve() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  phi[1] = 1; mu[1] = 1;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[cnt ++] = i;
      mu[i] = -1; phi[i] = i - 1;
    }
    for(int j = 0; j < cnt && prm[j] * (ll(i)) <= (ll(N)); j ++) {
      int v = prm[j] * i;
      vis[v] = true;
      if(i % prm[j] == 0) {
        mu[v] = 0; phi[v] = phi[i] * prm[j];
        break;
      } else {
        mu[v] = mu[i] * -1;
        phi[v] = phi[i] * phi[prm[j]];
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = phi_S[i - 1] + phi[i];
    mu_S[i] = mu_S[i - 1] + mu[i];
  }
}
__gnu_pbds::gp_hash_table<ll, ll> mu_d;
ll mu_sum(ll n) {
  if(n <= (ll(N))) return mu_S[n];
  if(mu_d.find(n) != mu_d.end()) {
    return mu_d[n];
  }
  ll ans = 1;
  for(ll i = 2; i <= n;) {
    ll nx = n / (n / i);
    ans -= (nx - i + 1LL) * mu_sum(n / i);
    i = nx + 1LL;
  }
  mu_d[n] = ans;
  return ans;
}
ll pre_sum(ll n) {
  return (n * (n + 1LL) / 2LL);
}
__gnu_pbds::gp_hash_table<ll, ll> phi_d;
ll phi_sum(ll n) {
  if(n <= (ll(N))) return phi_S[n];
  if(phi_d.find(n) != phi_d.end()) {
    return phi_d[n];
  }
  ll ans = pre_sum(n);
  for(ll i = 2; i <= n;) {
    ll nx = n / (n / i);
    ans -= (nx - i + 1LL) * phi_sum(n / i);
    i = nx + 1LL;
  }
  phi_d[n] = ans;
  return ans;
}

int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    int n; scanf("%d", &n);
    printf("%lld %lld\n", phi_sum(n), mu_sum(n));
  }
  return 0;
}