数论函数1

0xyz · 2023-07-16 20:16:27 · 个人记录

以下所有变量，如无特殊说明，均指代正整数。

一、积性函数基本定义

定义 1 数论函数：一个 \mathbb{N}^+\to\mathbb{C} 的单射。

定义 2 积性函数：一个数论函数 f，满足 \forall a,b\in \mathbb{N}^+,\gcd(a,b)=1,f(a)f(b)=f(ab).

定义 3 完全积性函数：一个数论函数 f，满足 \forall a,b\in\mathbb{N}^+,f(a)f(b)=f(ab)。

常见的积性函数：

常数函数 1(n)=1（完全积性函数）
单位函数 \epsilon(n)=[n=1]（完全积性函数）
指数函数 id_k(n)=n^k；恒等函数 id(n)=n（完全积性函数）
除数函数 \sigma_k(n)=\sum\limits_{d\mid n}d^k，\sigma_0(n) 一般表示为 d(n) 或 \tau(n)，\sigma_1(n) 一般表示为 \sigma(n)。
欧拉函数 \varphi(n)=\sum\limits_{i=1}\limits^{n}[\gcd(i,n)=1]。
莫比乌斯函数 \mu(n)=\begin{cases}1 &n=1\\0 &\exists d>1,d^2\mid n\\(-1)^{\omega(n)} &\text{otherwise}\end{cases}，其中 \omega(n)=\sum\limits_{i=1}^{\infty}[p_i\mid n]，即 n 的不同质因数个数。

对于 d(n) 和 \omega(n) 的范围参考下表。

定义 4 狄利克雷卷积（用 * 表示）是两个数论函数之间的运算：h=f*g 等同于 h(n)=\sum\limits_{d\mid n}f(d)\cdot g(\frac{n}{d})。

记住，这个狄利克雷卷积在数论函数相关的知识点中非常重要。

二、积性函数线性求值

我们在用欧拉筛的时候，保证了每个合数都是被它的最小质因子筛掉。利用这个性质，我们可以在 O(n) 的时间复杂度内求出积性函数 f 的 f(1) 到 f(n) 的值。

三、数论分块

从一道例题开始讲起：UVA11526 H(n)。

给定 n\le 10^9，要求 \sum\limits_{i=1}\limits^{n}\lfloor\frac{n}{i}\rfloor。

如果我们暴力求，时间复杂度 O(n)，但是这样比较慢。

我们发现一个性质：考虑 f(x)=\lfloor\frac{n}{x}\rfloor，对于 i=1\to \lceil\sqrt n\rceil-1，f(i) 一共最多 \lceil\sqrt n\rceil-1 个不同的值值；对于 i=\lceil\sqrt n\rceil\to n，f(i) 的值域为 1\to\big\lfloor\frac{n}{\lceil\sqrt n\rceil}\big\rfloor，一共最多 \big\lfloor\frac{n}{\lceil\sqrt n\rceil}\big\rfloor\le\lfloor\frac{n}{\sqrt n}\rfloor=\lfloor\sqrt n\rfloor 个不同的值。所以所有的 f(i) 一共至多 \lceil\sqrt n\rceil-1+\lfloor\sqrt n\rfloor\le2\lfloor\sqrt n\rfloor 个不同的值。

同时我们容易知道，值相同的一段数一定连续。那么我们就可以针对值相同的一段数进行“分块”，将一段数并在一起 O(1) 求解。我们考虑怎么由一个值段的左右端点 pl,pr 推出下一个值段的左右端点 ql,qr。容易知道 ql=pr+1，同时我们知道目标值段的值是 \lfloor\frac{n}{ql}\rfloor，所以 qr+1 是值为 k=\lfloor\frac{n}{qr+1}\rfloor=\lfloor\frac{n}{ql}\rfloor-1 的值段里最靠左的数，也就是满足以上条件的最小数。从而 qr+1>\lfloor\frac{n}{k+1}\rfloor=\Big\lfloor\frac{n}{\lfloor\frac{n}{ql}\rfloor}\Big\rfloor，因为 qr 最小，所以有 qr=\Big\lfloor\frac{n}{\lfloor\frac{n}{ql}\rfloor}\Big\rfloor。

于是我们可以写出代码了，对于一个 n，时间复杂度 O(\sqrt n)。

ll H(ll n){
    ll res=0;
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        res+=(r-l+1)*(n/l);
    }
    return res;
}

这只是一个例子，数论分块的核心思想就是在不同的值只有 O(\sqrt n) 个的时候，分成不同值域块分别处理。当然，具体左右端点要自己推出，有些时候不一样。

习题

P2261 [CQOI2007] 余数求和

给定 n,k\le 10^9，求 \sum\limits_{i=1}\limits^nk\bmod i。

转化一下，因为 k\bmod i=k-i\lfloor\frac{k}{i}\rfloor，所以 ans=nk-\sum\limits_{i=1}\limits^ni\lfloor\frac{k}{i}\rfloor。那么我们就是要求 \sum\limits_{i=1}\limits^n\lfloor\frac{k}{i}\rfloor。但是不同的值的个数明显是 O(n) 的，怎么办呢？我们发现 \lfloor\frac{k}{i}\rfloor 一共最多 O(\sqrt k) 种不同的值，所以针对 \lfloor\frac{k}{i}\rfloor 的值分段，每一段对答案的贡献就是它对应的 \lfloor\frac{k}{i}\rfloor 乘上这一段的下标的总和（可以用等差数列求和来计算）。然后我们分段时每一段的左端点 ql=pr+1，如果这一段对应的 \lfloor\frac{k}{i}\rfloor=0，那么这一段的 qr=n，否则这一段对应的 qr=\min(\Big\lfloor\frac{k}{\lfloor\frac{k}{ql}\rfloor}\Big\rfloor,n)，推出的方法类似。时间复杂度 O(\sqrt k)。

s=n*k;
for(ll l=1,r;l<=n;l=r+1){
    if(k/l)r=min(k/(k/l),n);
    else r=n;
    s-=(k/l)*(r-l+1)*(l+r)/2;
}

四、莫比乌斯反演

定理 \mathrm{I} \epsilon=1*\mu。

证明：假设 n=\prod\limits_{i=1}\limits^{k}p_i^{\alpha_i},m=\prod\limits_{i=1}\limits^{k}p_i，那么我们有 \sum\limits_{d\mid n}\mu(d)1(\frac{n}{d})=\sum\limits_{d\mid n}\mu(d)=\sum\limits_{d\mid m}\mu(d)=\sum\limits_{i=0}\limits^{k}(-1)^iC_k^i=(1+(-1))^k=[k=0]=[n=1]=\epsilon(n)。

定理 \mathrm{II}（莫比乌斯反演）如果 g(n)=\sum\limits_{d\mid n}f(d)，那么 f(n)=\sum\limits_{d\mid n}g(d)*\mu(\frac{n}{d})。

证明：g*\mu=g*\epsilon/1=g/1=f。

所以我们可以用以上性质来解题。

方案 1：我们看见 [\gcd(i,j)=k] 的条件，可以通过定理 \mathrm{I} 转化为 [k\mid\gcd(i,j)]，进一步转化为 [k\mid i\land k\mid j]，便于求解（详见习题部分）。

方案 2：如果 f 不好求，可以先求出它与 1 的狄利克雷卷积 g，然后再通过莫比乌斯反演求出 f。

习题。

五、杜教筛

从一道例题开始：P4213 【模板】杜教筛(Sum)。

给定一个数论函数 f，我们要求 s(n)=\sum\limits_{i=1}\limits^{n}f(i) 的值。

我们构造一个数论函数 g，因为 \sum\limits_{i=1}\limits^{n}(f*g)(i)=\sum\limits_{i=1}\limits^n\sum\limits_{d\mid i}g(d)f(\frac{i}{d})=\sum\limits_{i=1}\limits^{n}g(i)\sum\limits_{j=1}\limits^{\lfloor\frac{n}{i}\rfloor}f(j)=\sum\limits_{i=1}\limits^ng(i)s(\lfloor\frac{n}{i}\rfloor)，所以 g(1)s(n)=\sum\limits_{i=1}\limits^ng(i)s(\lfloor\frac{n}{i}\rfloor)-\sum\limits_{i=2}\limits^ng(i)s(\lfloor\frac{n}{i}\rfloor)=\sum\limits_{i=1}\limits^n(f*g)(i)-\sum\limits_{i=2}\limits^ng(i)s(\lfloor\frac{n}{i}\rfloor)。所以我们的目标就是找到一个合适的 g，使得 f*g 与 g 的前缀和都可以被快速计算。后面的那个值可以用数论分块计算，关于 s 的部分可以递归。

如果计算 f*g 和 g 的单点值是 O(1) 的，那么 T(n)=O(\sqrt n)+\sum\limits_{i=2}\limits^{\sqrt n}T(\lfloor\frac{n}{i}\rfloor)，从而 T(n)=O(n^{\frac{3}{4}})。如果我们用线性筛预处理出 s(1) 到 s(n^{\frac{2}{3}}) 的值，那么时间复杂度降为 O(n^{\frac{2}{3}})。