[HDU 5608]Function(莫比乌斯反演 + 杜教筛)

题目描述

有
求

只有最多组数据

题目分析

如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的值
令,根据莫比乌斯反演

于是用筛出前项就行了
总时间复杂度

AC code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 1000001;
const int mod = 1e9+7;
const int inv3 = 333333336;

inline int g(int n)
{
  return (1ll * n * n % mod - 3ll * n % mod + 2) % mod;
}

int Prime[MAXN], Cnt, mu[MAXN], f[MAXN];
bool IsnotPrime[MAXN];

void init()
{
  mu[1] = 1;
  for(int i = 2; i < MAXN; ++i)
  {
    if(!IsnotPrime[i]) Prime[++Cnt] = i, mu[i] = -1;
    for(int j = 1; j <= Cnt && i * Prime[j] < MAXN; ++j)
    {
      IsnotPrime[i * Prime[j]] = 1;
      if(i % Prime[j] == 0)
      {
        mu[i * Prime[j]] = 0;
        break;
      }
      mu[i * Prime[j]] = -mu[i];
    }
  }
  for(int i = 1; i < MAXN; ++i)
    for(int j = i; j < MAXN; j+=i)
      f[j] = (f[j] + 1ll * mu[j/i] * g(i) % mod) % mod;
  for(int i = 1; i < MAXN; ++i) f[i] = (f[i-1] + f[i]) % mod;
}
map<int,int>F;
inline int solve(int n)
{
  if(n < MAXN) return f[n];
  if(F.count(n)) return F[n];
  int ret = (1ll * n * (n+1) % mod * (n-4) % mod * inv3 % mod + 2ll*n%mod) % mod;
  for(int i = 2, j; i <= n; i=j+1)
  {
    j = n/(n/i);
    ret = (ret - 1ll * (j-i+1) * solve(n/i) % mod) % mod;
  }
  return F[n]=ret;
}

int main()
{
  init();
  int T, n;
  scanf("%d", &T);
  while(T--)
  {
    scanf("%d", &n);
    printf("%d\n", (solve(n)+mod)%mod);
  }
}