调和级数

调和级数（Harmonic series），其形式为：

\[H_n=\sum\limits_{i=1}^n\frac{1}{i}

\]

并且

\[\sum\limits_{i=1}^n\frac{1}{i}\approx\log n

\]

Proof：

简要的 Proof：

\[\sum\limits_{i=1}^n\frac{1}{i}=\sum\limits_{i=0}^{\log n}\sum\limits_{j=2^i}^{2^{i+1}-1}\frac{1}{j} \le 2^i\times \frac{1}{2^i}=1

\]

就是这么分个组：

\(\underline{1}\ \ \underline{\frac{1}{2}\ \ \frac{1}{3}}\ \ \underline{\frac{1}{4}\ \ \frac{1}{5}\ \ \frac{1}{6}\ \ \frac{1}{7}}\ \ \underline{\frac{1}{8}\ \ \frac{1}{9}\ \ \frac{1}{10}\ \ \frac{1}{11}\ \ \frac{1}{12}\ \ \frac{1}{13}\ \ \frac{1}{14}\ \ \frac{1}{15}}\)

然后每一组所有的数的和一定小于该组的数的数量与该组的第一个数的积。

例：\(\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}\le 4 \times \frac{1}{4}\)

更为严谨的公式：

\[H_n=\ln n+\gamma+o(1)

\]

其中 \(\ln n=\log_e n\)；\(\gamma\) 是欧拉-马歇罗尼常数，约为 \(0.57721\)；\(o(1)\) 是误差项，当 \(n\to\infty\) 时，\(o(1)\to 0\)（注意她不是常数）。

质数个数

\(n\) 以内的质数个数（表示为 \(\pi(n)\)）约为：

\[\pi(n)\approx\frac{n}{\ln n}

\]

Proof：

根据质数定理：

\[\lim\limits_{n\to\infty}\frac{\pi(n)}{\frac{n}{\ln n}}=1

\]

可以得出 \(\pi(n)\approx\frac{n}{\ln n}\)。

说了感觉跟没说一样

也就是说，每 \(\ln n\) 个数中，就可能出现一个质数。

于是暴力查找第一个大于（或小于）\(x\) 的质数的时间复杂度就是 \(\mathcal{O}(\ln x\sqrt{x})\) 的，当 \(x \le 10^{13}\) 时可以在 1s 内卡过（如果常数小的话）。

欧拉筛法（线性筛）

我们都会 \(\mathcal{O}(\sqrt{n})\) 的判断一个数是否是质数。

click to view the code

bool prime(int n) {

if (n==1) {return 0;}

for (int i=2;i<=n/i;i++) {

if (n%i==0) {return 0;}

}

return 1;

}

但是如果题目要求你生成 \([1,n]\) 中所有的质数该怎么办呢？\(\mathcal{O}(n\sqrt{n})\) 的暴力？

No，no，no。暴力太慢了，有没有更快的？

于是本章主角——欧拉筛法出现了。还有一个配角：埃式筛法

欧拉筛法（Euler's Sieve），就是用来筛质数的。她是埃氏筛法（Sieve of Eratosthenes）的改进，拥有更高的效率。

算法

时间复杂度

埃氏筛法

\(\mathcal{O}(n\log\log n)\)

欧拉筛法

\(\mathcal{O}(n)\)

基本原则

每个数只会被其最小的质数标记为非质数。

不会对同一个数进行多次标记。

算法流程

在跑欧拉筛法之前你需要一个储存素数的数组 \(p\) 和记录这个数是不是质数的数组 \(isp\)（除了 \(1\) 以外初始化为 true）。

算法流程如下：

\(i\) 从 \(2\) 开始向后遍历 \(n\)。

检查质数：

如果 \(isp_i\) 是 true，则 \(i\) 是质数，将其添加到 \(p\) 数组中。

标记倍数：

对于已经找到的质数集合 \(p\) 中的每一个元素 \(p_j\)：

计算 \(i \times p_j\)。

如果 \(i\times p_j>n\)，则停止标记。

将 \(isp_{i\times p_j}\) 设置为 false，表示 \(i\times p_j\) 这个数这辈子也当不上质数。

如果 \(i\) 是 \(p_j\) 的倍数（即 \(i\bmod p_j==0\)），则停止标记，以免像埃氏筛法一样重复标记。

于是欧拉筛法就跑完了。

其中 the most important part 是：

“如果 \(i\) 是 \(p_j\) 的倍数（即 \(p_j\mid i\)），则停止标记。”

这也是最难理解的地方。

Proof：

假设我们遍历到了数 \(i\)，其最小质因子是 \(j\)（\(j\mid i\)），我们已经筛出来的质数的集合是 \(S\)。

正着似乎不好证，那么使用反证法。

设 \(k>j\) 且 \(k\in S\)，我们尝试去标记 \(i\times k\)，可以发现 \(i\times k\) 可以表示为 \(\frac{i}{j}\times j\times k\)，\(j\) 比 \(k\) 小，故不满足原则 \(\verb!1!\)。

所以当 \(j\mid i\) 时，需要 break 掉。

click to view the code

int n;

int p[N];

bool isp[N];

void euler(int n) {

isp[1]=1;

for (int i=2;i<=n;i++) {

if (!isp[i]) {p[++p[0]]=i;}

for (int j=1;j<=p[0] && i*p[j]<=n;j++) {

isp[i*p[j]]=1;

if (i%p[j]==0) {break;}

}

}

}

注：代码中的 \(isp_i\) 为 false 时，表示 \(i\) 是质数。我偷懒的借口是为了省运行时间

算术基本定理（唯一分解定理）

对于任何一个 \(n\)（\(n\in \mathbb{N_+}\) 且 \(n>1\)），可表示为：

\[n=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_m^{c_m}=\prod\limits_{i=1}^m p_i^{c_i}

\]

其中 \(c_i\in \mathbb{N_+}\)，\(p_i\) 是质数，且 \(p_1

可以看出：一个数 \(n\)，她的大于 \(\sqrt{n}\) 的质因子最多只有一个且其指数一定是 \(1\)。

推论 \(\verb!I!\)

\(n\) 的正约数个数为：

\[cnt(n)=\prod\limits_{i=1}^m(c_i+1)

\]

Proof：

对于 \(n\) 的一个质因子 \(p_i\)，她的指数能从 \(0\) 到 \(c_i\) 中选取，故有 \(c_i+1\) 种可能性。再根据乘法原理，即可得出上述公式。

推论 \(\verb!II!\)

\(n\) 的所有正约数之和为：

\[\sigma(n)=\prod\limits_{i=1}^m(\sum\limits_{j=0}^{c_i}p_i^j)

\]

Proof：

每个正约数 \(d\) 可以唯一表示为：\(d=\prod\limits_{i=1}^m p_i^{k_i}\)

其中 \(0\le k_i \le c_i\)，即每个质因数的指数 \(k_i\) 独立地从 \(0\) 到 \(c_i\) 中选取，所以再次启用乘法原理，即可得到上述公式。

求 \(n\) 的正约数集合——试除法

根据算术基本定理理解即可，本算法过于简单，只给出代码。

click to view the code

int n,cnt;

int p[N],c[N];

void solve(int n) {

for (int i=2;i<=n/i;i++) {

if (n%i==0) {

p[++cnt]=i;

while (n%i==0) {

n/=i;

c[cnt]++;

}

}

}

if (n>1) {p[++cnt]=n;c[cnt]=1;}

}

求 \([1,n]\) 中每个数的正约数集合——倍数法

用试除法搞一个 \(\mathcal{O}(n\sqrt{n})\) 的暴力？

不，这太 low 了，有一种更优秀的算法——倍数法。

一个数 \(d\)，只有她的倍数才能拥有她这个约数，所以我们可以枚举一个 \(i\)，然后枚举 \(i\) 的所有倍数。

时间复杂度为 \(\mathcal{O}(n+\frac{n}{2}+\frac{n}{3}+\cdots+1)\)。

这是什么玩意？

等等，似乎有点眼熟。第一章讲的是什么？

于是你看了一下第一章的标题

哇！居然是调和级数！只不过这里乘上了一个 \(n\)。

于是时间复杂度为 \(\mathcal{O}(n\log n)\)，非常 nice。

click to view the code

vector d[N];

void solve(int n) {

for (int i=1;i<=n;i++) {

for (int j=i;j<=n;j+=i) {

d[j].push_back(i);

}

}

}

\(d_i\) 存的数即为 \(i\) 的所有约数。（顺序为升序）

推论：\([1,n]\) 中每个数的约数的个数的总和为 \(n\log n\)。

gcd and lcm

gcd 就是最大公约数，lcm 就是最小公倍数。

二者转换关系为：

\[\operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}

\]

其中 \(\forall a,b\in\mathbb{N}\)。

Proof：

设 \(a_0=\frac{a}{\gcd(a,b)},b_0=\frac{b}{\gcd(a,b)}\)。

那么 \(a_0\perp b_0,\operatorname{lcm}(a_0,b_0)=a_0\times b_0\)。

于是 \(\operatorname{lcm}(a,b)=\operatorname{lcm}(a_0\times\gcd(a,b),b_0\times\gcd(a,b))=a_0\times b_0\times \gcd(a,b)=\frac{a\times b}{\gcd(a,b)}\)。

更相减损术

\(\forall a,b\in\mathbb{N}\) 且 \(a\ge b\)。

\[\gcd(a,b)=\gcd(a,a-b)=\gcd(b,a-b)

\]

Proof：

对于一个 \(a,b\) 共有的约数 \(d\)。

\(\because d\mid a,d\mid b\)

\(\therefore d\mid (a-b)\)

所以 \(a,b\) 的公约数集合等于 \(a,a-b\) 或 \(b,a-b\) 的公约数集合。

辗转相除法（欧几里得算法）

\(\forall a,b\in\mathbb{N}\) 且 \(b\ne 0\)。

\[\gcd(a,b)=\gcd(b,a\bmod b)

\]

Proof：

分类讨论一下：

当 \(a

当 \(a\ge b\) 时：设 \(a=p\times b+r\)（\(0\le r

对于 \(a,b\) 共有的一个约数 \(d\)。

\(\because d\mid a,d\mid b\)

\(\therefore d\mid(a-p\times b)\)

即 \(d\mid r\)。

所以 \(a,b\) 的公约数集合等于 \(b,a\bmod b\) 的公约数集合。

辗转相除法的时间复杂度为 \(\mathcal{O}(\log(a+b))\)，比更相减损术要常用得多。但是进行高精度运算时还是推荐使用更相减损术，因为高精减比高精除容易实现。

click to view the code

int gcd(int a,int b) {

return b?gcd(b,a%b):a;

}

整除分块（数论分块）

定义：\(\forall i\in[1,n]\)（\(n\in\mathbb{N_+}\)），把 \(\lfloor\frac{n}{i}\rfloor\) 相等的 \(i\) 分到同一个块中。

比如，当 \(n=10\) 时：

原数列：\(1\ \ 2\ \ 3\ \ 4\ \ 5\ \ 6\ \ 7\ \ 8\ \ 9\ \ 10\)

对应的 \(\lfloor\frac{n}{i}\rfloor\) 的值为：\(\underline{10}\ \ \underline{5}\ \ \underline{3}\ \ \underline{2\ \ 2}\ \ \underline{1\ \ 1\ \ 1\ \ 1\ \ 1}\)

下取整的性质：若 \(\lfloor\frac{n}{x}\rfloor=y\)，则 \(\lfloor\frac{n}{y}\rfloor=x\)（\(x\le y\)）。

Proof：

\(\because \lfloor\frac{n}{x}\rfloor=y\)

\(\therefore n=x\times y+r\)（\(0\le r

\(\because r

\(\therefore \lfloor\frac{n}{y}\rfloor=x\)

定理：使用整除分块时，总块数不超过 \(2\sqrt{n}\)。

Proof：

分类讨论一下：

当 \(i\in[1,\sqrt{n}]\) 时：

可能的 \(\lfloor\frac{n}{i}\rfloor\) 的值的不同数量最多为 \(\sqrt{n}\)。

当 \(i\in(\sqrt{n},n]\) 时：

\(\because i\in(\sqrt{n},n]\)

\(\therefore \lfloor\frac{n}{i}\rfloor\le\frac{n}{i}<\frac{n}{\sqrt{n}}=\sqrt{n}\)

\(\therefore\lfloor\frac{n}{i}\rfloor\in[1,\sqrt{n})\)

那么可能的 \(\lfloor\frac{n}{i}\rfloor\) 的值的不同数量最多为 \(\sqrt{n}\)。

综上所述：

把以上两种情况的答案合并，于是总块数最多就是 \(2\sqrt{n}\)。

现在有这么一道题：求 \(\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor\)。

首先 \(\mathcal{O}(n)\) 的暴力你们 certainly 都会。

但是数据范围可以是 \(n\le 10^{15}\)。

考虑到总块数最多只有 \(2\sqrt{n}\)，我们尝试一个块一个块的遍历。

设一个块的左端点为 \(l\)，右端点为 \(r\)。

\(l\) 好搞，初始值赋为 \(1\)，每次 \(l=r+1\) 来跳转到下一个块的左端点。

但是 \(r\) 似乎不太好搞，怎么办呢？

右端点公式：\(r=\left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor\)

Proof：

设 \(k=\lfloor\frac{n}{l}\rfloor\)。

\(r\) 就是满足 \(\lfloor\frac{n}{i}\rfloor=k\) 的最大的 \(i\)（定义）。

\(n\) 可以表示为 \(k\times r+z\)（\(0\le z

考虑使用反证法。

若 \(z\ge k\)，那么 \(n\) 显然还能表示为 \(k\times(r+1)+z-k\)，\(r\) 也能被 \(r+1\) 替代，不符合 \(r\) 的定义。

故命题成立。

于是，我们就可以 \(\mathcal{O}(\sqrt{n})\) 的求解上面的问题了。

click to view the code

ll solve(ll n) {

ll res=0;

for (ll l=1,r;l<=n;l=r+1) {

r=n/(n/l);

ans+=(n/l)*(r-l+1);

}

return res;

}

有时需要注意处理块内值为 \(0\) 或 \(r\) 超出上界 \(n\) 的情况：

click to view the code

ll solve(ll n) {

ll res=0;

for (ll l=1,r;l<=n;l=r+1) {

if (k/l==0) {break;}

else {r=min(n,k/(k/l));}

res+=(k/l)*(r-l+1);

}

return res;

}

欧拉函数

定义：就是求 \([1,n]\) 中与 \(n\) 互质的数的个数，记为 \(\varphi(n)\)，那么

\[\varphi(n)=\sum\limits_{i=1}^n[i\perp n]

\]

但是这样求时间复杂度是 \(\mathcal{O}(n\log n)\) 的，效率较低。

那么，我们需要一个更为优秀的做法：

\[\varphi(n)=n\times\prod\limits_{i=1}^m(1-\frac{1}{p_i})=n\times\prod\limits_{i=1}^m(\frac{p_i-1}{p_i})

\]

Proof

根据算术基本定理，\(n\) 可以被分解为 \(\prod\limits_{i=1}^m p_i^{c_i}\)。

假如 \(n\) 只有一个质因子 \(p\)，那么 \([1,n]\) 中不与 \(n\) 互质的数就只能是 \(p\) 的倍数，显然：\(\varphi(n)=n-\frac{n}{p}\)。

假如 \(n\) 还有一个质因子 \(q\)，那么 \([1,n]\) 中不与 \(n\) 互质的数就只能是 \(p\) 或 \(q\) 的倍数，根据容斥原理，则：

\[\begin{aligned}

\varphi(n)&=n-\frac{n}{p}-\frac{n}{q}+\frac{n}{p\times q}\\

&=n\times(1-\frac{1}{p}-\frac{1}{q}+\frac{1}{p\times q})\\

&=n\times(1-\frac{1}{p})\times(1-\frac{1}{q})

\end{aligned}\]

第二步到第三步用的是十字相乘。

推广到一般情况，则可以得到：

\[\varphi(n)=n\times\prod\limits_{i=1}^m(1-\frac{1}{p_i})=n\times\prod\limits_{i=1}^m(\frac{p_i-1}{p_i})

\]

特别地，\(\varphi(1)=1\)。

还可以这样理解这个式子：

对于 \(n\) 的一个质因子 \(p\)，她的倍数在 \([1,n]\) 中的占比为 \(\dfrac{\frac{n}{p}}{n}=\frac{1}{p}\)，这些数是我们需要排除掉的，所以剩下的数的占比就是 \(1-\frac{1}{p}\)，使用乘法原理，我们就得到了剩余的数的占比 \(\prod\limits_{i=1}^n(1-\frac{1}{p_i})\)，最后再乘上一个 \(n\)，就完美结束了。

利用质因数分解求出所有的质因子，我们就有了一个 \(\mathcal{O}(\sqrt{n})\) 的求 \(\varphi(n)\) 的方法了。

click to view the code

int phi(int n) {

if (n==1) {return 1;}

int res=n;

for (int i=2;i<=n;i++) {

if (n%i!=0) {continue;}

res=res/i*(i-1);

while (n%i==0) {n/=i;}

}

return res;

}

性质

\(\forall n>1\)，\([1,n]\) 中与 \(n\) 互质的数的和为 \(\frac{n\times\varphi(n)}{2}\)。

Proof：

对于 \(\forall i\in[1,n]\)，若 \(i\perp n\)，则 \(\gcd(i,n)=\gcd(n-i,n)=1\)。所以与 \(n\) 互质的数是成对存在的，并且她们的平均数为 \(\frac{n}{2}\)，那么 \([1,n]\) 中与 \(n\) 互质的数的和就是平均数乘上其个数 \(\varphi(n)\)。

\(\varphi(n)\) 是积性函数。

积性函数：若 \(a\perp b\) 且 \(f(n)\) 是积性函数，有 \(f(a\times b)=f(a)\times f(b)\)。

完全积性函数：\(\forall a,b\in\mathbb{N_+}\)，有 \(f(a\times b)=f(a)\times f(b)\)。

性质：对 \(n\) 进行质因数分解，\(n=\prod\limits_{i=1}^m p_i^{c_i}\)，有 \(f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})\)。

Proof（性质 \(\verb!2!\)）：

若 \(a\perp b\)，则 \(a,b\) 之间没有相同的质因子。

对 \(a,b\) 进行质因数分解，\(a=\prod\limits_{i=1}^{m_1}p_i^{c_i},b=\prod\limits_{i=1}^{m_2}q_i^{c_i}\)。

则 \(\varphi(a\times b)=a\times\prod\limits_{i=1}^{m_1}(1-\frac{1}{p_i})\times b\times\prod\limits_{i=1}^{m_2}(1-\frac{1}{q_i})=\varphi(a)\times\varphi(b)\)。

设 \(n=p^k\)（\(p\) 是质数），则 \(\varphi(n)=p^k-p^{k-1}=p^{k-1}\times(p-1)\)。

Proof：

因为 \(n\) 就只有 \(p\) 这一个质因子，所以与 \(n\) 不互质的数一定都是 \(p\) 的倍数。\(p\) 的倍数的个数为 \(\frac{n}{p}=\frac{p^k}{p}=p^{k-1}\)，所以 \(\varphi(n)=n-p^{k-1}=p^k-p^{k-1}=p^{k-1}\times(p-1)\)。

若 \(p\) 是质数且 \(p\mid n\)，则 \(\varphi(p\times n)=p\times\varphi(n)\)。

Proof：

对 \(p,p\times n\) 进行质因数分解，可以发现她们的质因子集合是相同的，所以 \(\varphi(p\times n)=p\times n\times\prod\limits_{i=1}^m(1-\frac{1}{p_i})=p\times\varphi(n)\)。

若 \(p\) 是质数且 \(p\nmid n\)，则 \(\varphi(p\times n)=(p-1)\times\varphi(n)\)。

\(\mathcal{Proof}\ \verb!1!\)：

与上个性质的证明相似，对 \(p\times n,n\) 进行质因数分解（\(n=\prod\limits_{i=1}^m q_i^{c_i}\)），可以发现 \(p\times n\) 的质因子集合比 \(n\) 多了一个 \(p\)，所以 \(\varphi(p\times n)=p\times n\times\prod\limits_{i=1}^m(1-\frac{1}{q_i})\times\frac{p-1}{p}=(p-1)\times\varphi(n)\)。

\(\mathcal{Proof}\ \verb!2!\)：

因为 \(p\) 是质数，所以 \(\varphi(p)=p-1\)。

并且 \(n\) 和 \(p\) 是互质的。

于是 \(\varphi(p\times n)=\varphi(p)\times\varphi(n)=(p-1)\times\varphi(n)\)。

\(\sum\limits_{d\mid n}\varphi(d)=n\)。

Proof：

设 \(f(n)=\sum\limits_{d\mid n}\varphi(d)\)。

设 \(n\perp m\)，那么 \(n\) 和 \(m\) 没有相同的质因子，则：

\[\begin{aligned}

f(n)\times f(m)&=\left(\sum\limits_{d\mid n}\varphi(d)\right)\times\left(\sum\limits_{d\mid m}\varphi(d)\right)\\

&=\sum\limits_{d_1\mid n}\sum\limits_{d_2\mid m}(\varphi(d_1)\times\varphi(d_2))\\

&=\sum\limits_{d_1\mid n}\sum\limits_{d_2\mid m}\varphi(d_1\times d_2)\\

&=\sum\limits_{d\mid n\times m}\varphi(d)\\

&=f(n\times m)

\end{aligned}\]

即 \(f(n)\times f(m)=f(n\times m)\)。

所以 \(f(n)\) 是积性函数。

可以得到 \(f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})\)。

再进一步拆分 \(f(p^k)\)（性质 \(\verb!3!\) 在这里用上）：

\[\begin{align*}

f(p^k)&=\sum\limits_{i=0}^k\varphi(p^i)\\

&=1+\sum\limits_{i=1}^k(p^i-p^{i-1})\\

&=1-1+p-p+p^2-p^2+p^3+\cdots-p^{k-1}+p^k\\

&=p^k

\end{align*}\]

所以 \(f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})=\prod\limits_{i=1}^m p_i^{c_i}=n\)。

即 \(\sum\limits_{d\mid n}\varphi(d)=n\)。

线性求欧拉函数

根据性质 \(\verb!4!\) 和性质 \(\verb!5!\) 对欧拉筛法进行一点修改即可。

click to view the code

void euler(int n) {

phi[1]=1;

for (int i=2;i<=n;i++) {

if (!isp[i]) {

p[++p[0]]=i;

phi[i]=i-1;

}

for (int j=1;j<=p[0] && i*p[j]<=n;j++) {

isp[i*p[j]]=1;

if (i%p[j]==0) {

phi[i*p[j]]=phi[i]*p[j];

break;

}

else {

phi[i*p[j]]=phi[i]*(p[j]-1);

}

}

}

}

---

入门中的入门--如何拍摄银河
羽绒服上有很多褶皱，太丑啦！4招轻松去皱！