Min25筛

首先有个大前提就是f(x)在x为质数而且质数幂处的取值很好求出

$G_{i,j}$ 表示前i个数然后最小质因子大于 $prime_j$ 或者为质数的那些数的g函数之和

g函数是f在素数幂处的取值

然后 $F_{i,j}$ 为前i个数然后最小质因子大于等于 $prime_j$ ,的那些数的f函数之和

$prime_j$ 为第j个质数是什么

然后咋搞掉这两个函数呢?

设 $lpf(x)$ 为x的最小质因子

$G_k(i)=G_{k-1}(i)-[p_k^2\leq n]g(p_k)(G_{k-1}(\frac{n}{p_k})-G_{k-1}(p_{k-1}))$

其中第二部分剪掉的是我们考虑钦定这个 $p_k$ 已经出现了,然后剩下质因子随便选择,就是先除掉 $p_k$ ,然后剩下的只需要满足选的最小质因子大于j-1(被包含在前面中)即可

但是说你想想就会多减去一些部分,就是那些小于 $p_k$ 的质数qaq,他们显然不需要多减去,因为我们只要减去最小质因子恰好为 $p_k$ 的

所以说加上的就是 $g(p_k)G_{k-1}(p_{k-1})$ ,相当于提出了一些信息,之后钦定剩下的都是小于他的质数就好了

然后再看看我们该怎么去转移剩下的f啊QAQ

F_{k}(n)=\sum_{k\leq i,p_i^2\leq n}\sum_{c\geq 1,p_i^{c+1}\leq n}(f(p_i^c)F_{i+1}(\frac{n}{p_i^c})+f(p_i^{c+1}))+F_{prime}(n)-F_{prime}(p_k-1)

怎么理解这个式子?

...考虑我们还是好好推

$F_{k}(n)=\sum_{i=2}^n[p_k\leq lpf(i)]f(i)$

所以我们第一步可以考虑第k个质数加入后怎么算啊

枚举最小质因子是i,然后我们让 $n/p_{i+1}$ ,并且最小质因子要大于这个i,所以是 $Fi+1$ 就是左边的式子

然后显然可知我们要对于大于他们的只有一个质数的质数幂算上贡献,就是后面 $f_{p_i^{c+1}}$

然后那个类似前缀差的就是只算素数而不是素数幂

然后最后我们只需要计算 $Fprime$

首先会发现只有 $O(\sqrt n)$ 个取值有用

然后每个 $p^{c_i}$ 对于一个 $F_{prime}$ 贡献为 $a_i\sum p^{c_{i}}$

所以分开算每个 $p^{c_i}$ 的贡献即可

就是我们的G函数的定义了

很毒瘤啊

/* 「LOJ #6053」简单的函数 */
#include <algorithm>
#include <cmath>
#include <cstdio>

using i64 = long long;

constexpr int maxs = 200000;  // 2sqrt(n)
constexpr int mod = 1000000007;

template <typename x_t, typename y_t>
inline void inc(x_t &x, const y_t &y) {
  x += y;
  (mod <= x) && (x -= mod);
}
template <typename x_t, typename y_t>
inline void dec(x_t &x, const y_t &y) {
  x -= y;
  (x < 0) && (x += mod);
}
template <typename x_t, typename y_t>
inline int sum(const x_t &x, const y_t &y) {
  return x + y < mod ? x + y : (x + y - mod);
}
template <typename x_t, typename y_t>
inline int sub(const x_t &x, const y_t &y) {
  return x < y ? x - y + mod : (x - y);
}
template <typename _Tp>
inline int div2(const _Tp &x) {
  return ((x & 1) ? x + mod : x) >> 1;
}
template <typename _Tp>
inline i64 sqrll(const _Tp &x) {
  return (i64)x * x;
}

int pri[maxs / 7], lpf[maxs + 1], spri[maxs + 1], pcnt;

inline void sieve(const int &n) {
  for (int i = 2; i <= n; ++i) {
    if (lpf[i] == 0)
      pri[lpf[i] = ++pcnt] = i, spri[pcnt] = sum(spri[pcnt - 1], i);
    for (int j = 1, v; j <= lpf[i] && (v = i * pri[j]) <= n; ++j) lpf[v] = j;
  }
}

i64 global_n;
int lim;
int le[maxs + 1],  // x \le \sqrt{n}
    ge[maxs + 1];  // x > \sqrt{n}
#define idx(v) (v <= lim ? le[v] : ge[global_n / v])

int G[maxs + 1][2], Fprime[maxs + 1];
i64 lis[maxs + 1];
int cnt;

inline void init(const i64 &n) {
  for (i64 i = 1, j, v; i <= n; i = n / j + 1) {
    j = n / i;
    v = j % mod;
    lis[++cnt] = j;
    idx(j) = cnt;
    G[cnt][0] = sub(v, 1ll);
    G[cnt][1] = div2((i64)(v + 2ll) * (v - 1ll) % mod);
  }
}

inline void calcFprime() {
  for (int k = 1; k <= pcnt; ++k) {
    const int p = pri[k];
    const i64 sqrp = sqrll(p);
    for (int i = 1; lis[i] >= sqrp; ++i) {
      const i64 v = lis[i] / p;
      const int id = idx(v);
      dec(G[i][0], sub(G[id][0], k - 1));
      dec(G[i][1], (i64)p * sub(G[id][1], spri[k - 1]) % mod);
    }
  }
  /* F_prime = G_1 - G_0 */
  for (int i = 1; i <= cnt; ++i) Fprime[i] = sub(G[i][1], G[i][0]);
}

inline int f_p(const int &p, const int &c) {
  /* f(p^{c}) = p xor c */
  return p xor c;
}

int F(const int &k, const i64 &n) {
  if (n < pri[k] || n <= 1) return 0;
  const int id = idx(n);
  i64 ans = Fprime[id] - (spri[k - 1] - (k - 1));
  if (k == 1) ans += 2;
  for (int i = k; i <= pcnt && sqrll(pri[i]) <= n; ++i) {
    i64 pw = pri[i], pw2 = sqrll(pw);
    for (int c = 1; pw2 <= n; ++c, pw = pw2, pw2 *= pri[i])
      ans +=
          ((i64)f_p(pri[i], c) * F(i + 1, n / pw) + f_p(pri[i], c + 1)) % mod;
  }
  return ans % mod;
}

int main() {
  scanf("%lld", &global_n);
  lim = sqrt(global_n);

  sieve(lim + 1000);
  init(global_n);
  calcFprime();
  printf("%lld\n", (F(1, global_n) + 1ll + mod) % mod);

  return 0;
}

夏晓光(loveJY)的博客

首先有个大前提就是f(x)在x为质数而且质数幂处的取值很好求出

20省选Day4