笔记 - Powerful number 与 Powerful number 筛

发表于 更新于 分类于 ， 本文字数： 499 阅读时长 ≈ 2 分钟

Powerful number 筛是一种能在最佳 \(O(\sqrt n)\) 的时间下求一类积性函数前缀和的不稳定方法

Powerful number

定义 - 1-1 Powerful number

令 \(n\in\mathbb{Z}\) 的唯一分解式为 \(n=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}\), 若 \(\forall i\in[1,\omega(n)]_{\mathbb{N}},~\alpha_i>1\), 则称 \(n\) 为 Powerful number

Powerful number 有如下性质

定理 - 1-1 \(n\) 为 Powerful number \(\iff~\exists a,b\in\mathbb{Z}, n=a^2b^3\)

Proof

令 \(P_n:=\{(p_i,\alpha_i):p_i\in\text{Prime}^+,~p_i^{\alpha_i}\mid n,~p_i^{\alpha_i+1}\nmid n\}\)

  • \(\implies\):

    令

    • \(P_1'=\{(p_i,\alpha_i)\in P_n:2\mid\alpha_i\}\)
    • \(P_2'=\{(p_i,\alpha_i)\in P_n:2\nmid\alpha_i\}\)

    则

    \[ P_n=P_1'\cup P_2',~P_1'\cap P_2'=\varnothing \]

    令

    • \[ a=\prod_{(p,\alpha)\in P_1'}p^\frac{\alpha}{2}\prod_{(p,\alpha)\in P_2'}p^\frac{\alpha-3}{2} \]
    • \[ b=\prod_{(p,\alpha)\in P_2'}p \]

    则

    \[ n=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}=a^2b^3 \]

  • \(\impliedby\):

    \[ n=a^2b^3=\prod_{(p,\alpha)\in P_a}p^{2\alpha}\cdot\prod_{(p,\alpha)\in P_b}p^{3\alpha}=\prod_{(p,\alpha)\in P_n}p^\alpha \]

    不难发现 \(\forall(p,\alpha)\in P_n,\alpha>1\)

定理 - 1-2

\[ |\{m\in\mathbb{Z}_n:m~\text{is}~\text{powerful}~\text{number}\}|=O(\sqrt{n}) \]

Proof

\[ |\{m\in\mathbb{Z}_n:m~\text{is}~\text{powerful}~\text{number}\}|=O\left(\int_1^{\sqrt{n}}\sqrt[3]{\frac{n}{x^2}}\mathrm{d}x\right)=O(\sqrt{n}) \]

Powerful number 筛

对积性函数 \(f\), 我们要找到积性函数 \(g\) 满足 \(g(p)=f(p)\)

令积性函数 \(h=f*g^{-1}\)

显然，\(f(p)=h(p)g(1)+h(1)g(p)=h(p)+f(p)\), 故 \(h(n)\ne 0\implies n\) 为 Powerful number

我们有

\[ \sum_{i=1}^nf(i)=\sum_{i=1}^n(h*g)(i)=\sum_{i=1}^nh(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(j) \]

所以只需枚举 \(O(\sqrt{n})\) 个 Powerful number, 暴力求出对应的 \(h\) 值，并求 \(g\) 的前缀和即可求出 \(f\) 的前缀和

模板

Show code

main.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Usage:
// - set n
// - run dfs(1, 1, 1);
// - the result is ans

// requires:
// - N: Count of prime
// - P: Max exponent
// - prime[]: Primes, started at prime[1] = 2
// - get_sum(n): Return $\sum_{i=1}^n g(i)$, usually use Du's method
// - F(i, now_exp): Return $f(p_i^q)$, which $p_i$ means prime[i] and $q$ means
// now_exp
// - G(i, now_exp): Return $f(p_i^q)$, which $p_i$ means prime[i] and $q$ means
// now_exp
i64 ans, n;
bool vis_h[N][P];
i64 h[N][P];
void dfs(i64 now_x, i64 now_h, i64 idx_prime) {
  ans = (ans + now_h * get_sum(n / now_x) % MOD) % MOD;
  if (idx_prime > 1 && now_x > n / prime[idx_prime] / prime[idx_prime]) return;
  _for(i, idx_prime, cnt_prime) {
    if (i > 1 && now_x > n / prime[i] / prime[i]) break;
    for (i64 now_exp = 1, next_x = now_x * prime[i]; next_x <= n;
         ++now_exp, next_x *= prime[i]) {
      if (!vis_h[i][now_exp]) {
        i64 f = F(i, now_exp), g = G(i, 1);
        _for(j, 1, now_exp) {
          f = ((f - g % MOD * h[i][now_exp - j] % MOD) % MOD + MOD) % MOD;
          //! Changing this depending on the problem recommended
          g = G(i, j + 1);
        }
        h[i][now_exp] = f;
        vis_h[i][now_exp] = 1;
      }
      if (h[i][now_exp]) dfs(next_x, h[i][now_exp] * now_h % MOD, i + 1);
    }
  }
}

例题

  1. LOJ 6053 简单的函数 -> 题解

参考资料