速通莫反

wallace_QwQ · 2025-06-11 17:19:41 · 算法·理论

一.积性函数

TIP. 其实这部分并不是太重要，只需要记得这些函数的定义和怎么用线性筛 O(n) 求解即可。

(1).定义

积性函数：对于函数 f(x)，若 \forall a,b\in\mathbb{N}^+,\gcd(a,b)=1,f(ab)=f(a)f(b)，则称 f(x) 为积性函数。

完全积性函数：对于函数 f(x)，若 \forall a,b\in\mathbb{N}^+,f(ab)=f(a)f(b)，则称 f(x) 为完全积性函数。

• 常见的积性函数：\varphi,\mu,\sigma,d
• 常见的完全积性函数：\varepsilon,I,id

其中：\varepsilon(n)=\left[n=1\right],I(n)=1,id(n)=n

积性函数的性质：

• 设 n=\prod p_i^{\alpha_i}，那么 f(n)=\prod f(p_i^{\alpha_i})
  • 于是可以用线性筛求出 g(n)=p_1^{\alpha_1}，然后 f(n)=f(g(n))f(\frac{n}{g(n)})，在 O(n) 时间内预处理积性函数的值。
• 若 f(n)，g(n) 都是积性函数，那么 fg，\frac{f}{g} 都是积性函数。

  (2).欧拉函数 \varphi

  1.定义

  若 n=\prod_{i=1}^{s}{p_i}^{k_i}，其中 p_i 为质数，则 \varphi(n)=n\prod_{i=1}^{s}\frac{p_i-1}{p_i}，表示小于等于 n 和 n 互质的数的个数$

  2.性质：

  1. 若n为质数，\varphi(n)=n-1
  2. 若n为奇数，\varphi(n)=\varphi(2n)
  3. 若a \perp b,\varphi(ab)=\varphi(a)\varphi(b)
  4. n=\sum_{d \mid n}\varphi(d)
  5. 若n=p^k,且p为质数，\varphi(n)=p^k-p^{k-1}

     3.求法

     a.单个：

     int euler_phi(int n){
     int ans=n,sq=sqrt(n);
     for1(i,2,sq)
     if(n%i==0){
         ans=ans/i*(i-1);
         while(n%i==0) n/=i;
     }
     if(n>1) ans=ans/n*(n-1);
     return ans;
     }

     b.多个：

     筛法： 设p_1为n的最小质因子，n'=\frac{n}{p_1}，显然有\varphi(p_1)=p_1-1 若n'\bmod p_1=0,\varphi(n)=p_1*\varphi(n') 若n'\bmod p_1\ne0,\varphi(n)=\varphi(p_1)*\varphi(n')

     void euler_phi(int n){
     phi[1]=1;
     for1(i,2,n){
     if(!vis[i]) pri.p_b(i),phi[i]=i-1;
     for(int j: pri){
     if(i>n/j) break;
     vis[i*j]=1;
     if(i%j==0){
     phi[i*j]=phi[i]*j;
     break;
     }
     phi[i*j]=phi[i]*phi[j];
     }
     }
     }

     (3).莫比乌斯函数 \mu

     1.定义

     \mu(n)= \begin{cases} 1&n=1\\ 0&n的质因子最高次数>1\\ (-1)^k&n的质因子最高次数=1 \end{cases}

     其中 k 为 n 的质因子个数。

     2.性质

     \begin{cases} 1&n=1\\ 0&n\ne1 \end{cases}

     即 \sum\limits_{d\mid n}\mu(d)=\varepsilon(n),\mu\ast1=\varepsilon

     3.求法

     线性筛：

     void get_mu(int n){
     mu[1]=1;
     for1(i,2,n){
     if(!vis[i]) pri.p_b(i),mu[i]=-1;
     for(int j: pri){
     if(i>n/j) break;
     vis[i*j]=1;
     if(i%j==0){
     mu[i*j]=0;
     break;
     }
     mu[i*j]=-mu[i];
     }
     }
     }

     (4).约数之和 \sigma 与 约数个数 d

     1.定义

     若 n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\dots p_n^{\alpha_n}

则：

2.求法

1. 线性筛求 d

若可以 O(1) 计算 f(r)-f(l) 时。

我们考虑将 \lfloor\frac{n}{i}\rfloor 相同的数分块计算以使复杂度降至 O(\sqrt n\times poly(n))

其中的 poly(n) 是计算 g(i) 一次的复杂度。

最简单的例子： \sum_{i=1}^n\lfloor\frac{n}{i}\rfloor

证：按 \lfloor\frac{n}{i}\rfloor 相同的数分块数是 \sqrt{n} 量级的。

若 i\le \sqrt{n} 则 \lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{1}\rfloor\dots\lfloor\frac{n}{\sqrt{n}}\rfloor\ge\sqrt{n} 最多有 \sqrt{n} 个取值。

若 i> \sqrt{n} 则 \lfloor\frac{n}{i}\rfloor<\sqrt{n} 最多有 \sqrt{n} 个取值。

证毕。

所以数论整除可以将 O(n) 降为 O(\sqrt{n})

例题：UVA11526 H(n)

LL H(LL n){
    LL ans=0;
    for(LL i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans+=(j-i+1)*(n/i);
    }
    return ans;
}

三.狄利克雷卷积

• 两个数论函数的狄利克雷卷积：
• \begin{aligned} (f\ast g)(n) &=\sum\limits_{d\mid n}f(d)g(\frac{n}{d})\\ &=\sum\limits_{a\cdot b=n}f(a)g(b) \end{aligned}

\begin{aligned} \epsilon=\mu\ast1&\iff\epsilon(n)=\sum\limits{d\mid n}\mu(d)\ d=1\ast1&\iff d(n)=\sum\limits{d\mid n}1\ \sigma=id\ast1&\iff\sigma(n)=\sum\limits{d\mid n}d\ \varphi=\mu\ast id&\iff\varphi(n)=\sum\limits{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned}

\begin{aligned} &\sum\limits{i=1}^n(f\ast g)(i)\ &=\sum\limits{i=1}^n\sum\limits{d\mid i}f(d)g(\frac{i}{d})\ &=\sum\limits{d=1}^n g(d)\sum\limits{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\ &=\sum\limits{d=1}^n g(d)sf(\lfloor\frac{n}{d}\rfloor) \end{aligned}