部分数论学习笔记

标签：lfloor frac gcd 数论 lim sum 笔记 学习 rfloor

数论分块

若可以 \(O(1)\) 计算 \(f(r) - f(l)\)，那么就可以 \(O(\sqrt n)\) 计算 \(\sum^n_{i = 1} f(i)(g\lfloor\frac{n}{i}\rfloor)\)。

关于 \(l , r\) 的含义与计算：

含义：\(\forall x \in [l,r],\lfloor\frac{n}{x}\rfloor\) 相等

计算：刚开始 \(l\) 肯定为 \(1\)，如何理解 \(r=\lfloor \frac{lim}{\lfloor \frac{lim}{l} \rfloor} \rfloor\) 呢？

首先 \(\lfloor \frac{lim}{l} \rfloor\) 肯定是好理解的，因为要使得 \(\lfloor \frac{n}{x} \rfloor = \lfloor \frac{lim}{l} \rfloor\)，那么 \(r\) 就是这里面最大的 \(x\)，设 \(lim \% {\lfloor \frac{lim}{l} \rfloor} = y\)，若 \(r\) 要增大 \(1\)，那么 \(lim\) 相应的要增大 \(\lfloor \frac{lim}{l} \rfloor - y\) 才能堪堪达到。

狄利克雷卷积

\(h = f * g\)

\(h(x) = \sum_{d|x}f(x)g(\frac{x}{d})\)

积性函数

单位函数 \(\epsilon(x) = [x = 1]\)

恒等函数 \(id(x) = x\)

常数函数 \(1(n) = 1\)

性质1 \(\varphi * 1 = id\)

性质2 \(id * \mu = \varphi\)

证明晚点证

莫比乌斯反演

一个重要性质 \(\sum_{d|n} \mu(d) = \begin{cases} 1 & \text{if} & n \\ 0 & \text{if} & {n = 1} \end{cases}\)

对应到 \(\gcd\) 上就是 \(\sum_{d|\gcd(i,j)} \mu(d) = [\gcd(i,j) = 1]\)

这样看起来变复杂了，但是我们就可以在前面 \(\sum_i \sum_j\) 两层东西前面枚举 \(d\) 具体是什么，以此改变了枚举顺序，并且d仅是 \(i , j\) 的公约数而非最大公约数。

以一道例题来说

GCD SUM P2398

\[\begin{aligned} {} & \sum_{i=1}^n \sum_{j=1}^n \gcd(i, j) \\ = & \sum_{x=1}^n x \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j) = x] \\ = & \sum_{x=1}^n x \sum_{i=1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{x} \rfloor} [\gcd(i,j) = 1] \\ = & \sum_{x=1}^n x \sum_{d=1}^{\lfloor \frac{n}{x} \rfloor} \mu(d) {\lfloor \frac{\lfloor \frac{n}{x} \rfloor}{d} \rfloor}^2 \end{aligned} \]

标签：lfloor,frac,gcd,数论,lim,sum,笔记,学习,rfloor
From： https://www.cnblogs.com/TongKa/p/18235965