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

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

先考虑求欧拉函数的前缀和，我们先找一个它的卷积（这里用\(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;
}

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