首先这个题和能量采集几乎完全一致……稍微有点反演常识的人都知道答案事\(\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;
}

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