数论详解
__O_v_O__
·
2025-02-07 08:41:01
·
算法·理论
欧几里得算法
辗转相除法
更相减损术
\gcd(a,b)=\gcd(a-b,b)
欧几里得算法
\gcd(a,b)=\gcd(b,a\bmod b)
注意到当 a>b 时 a\bmod b<\frac{1}{2}a ，所以至多递归 O(\log a) 层。
扩展欧几里得算法
求不定方程 ax+by=m 的一组整数解。
sol:
该方程有解当且仅当 \gcd(a,b)\mid m ，下面假设 d=\gcd(a,b) ，则原方程可化为 ax+by=d 。
设：
ax+by=\gcd(a, b)
bx_1+(a\bmod b)y_1=\gcd(b,a\bmod b)
假设我们已经求出 x_1 和 y_1 ，考虑得到 x 和 y 。
由欧几里得定理可知：\gcd(a,b)=\gcd(b,a\bmod b) 。
所以：ax+by=bx_1+(a\bmod b)y_1 。
又因为：
a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b
所以：
ax+by=bx_1+\left(a-\left\lfloor\frac{a}{b}\right\rfloor\times b\right)y_1
整理得：
ax+by=ay_1+b\left(x_1−\left\lfloor\frac{a}{b}\right\rfloor y_1\right)
对比两侧系数即得到：
x=y_1,y=x_1−\left\lfloor\frac{a}{b}\right\rfloor y_1
递归调用即可，边界是 b=0 时，此时取 x=1,y=0 。
类欧几里得算法
给定 n,a,b,c ，分别求：
\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor,\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2,\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor
sol:
令 f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor ，考虑 a,b,c 的关系。
两种情况递归即可，复杂度同欧几里得算法，为 O(\log n) 。
现在，我们还需要求：g(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor 和 h(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2 。
先求 g ，同样分两种情况。
若 a\ge c 或 b\ge c ：\
与 f 类似，推导出 g(a,b,c,n)=\frac{n(n+1)(2n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor+g(a\bmod c,b\bmod c,c,n) 。
若 a<c 且 b<c ：\
方便起见，设 $t=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor$，则：\
$\begin{aligned}g(a,b,c,n)&=\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^ni[i>t]\\&=\sum\limits_{j=0}^{m-1}\frac{1}{2}(t+n+1)(n-t)\\&=\frac{1}{2}\left[mn(n+1)-\sum\limits_{j=0}^{m-1}t^2-\sum\limits_{j=0}^{m-1}t\right]\\&=\frac{1}{2}\left[m n(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\right]\end{aligned}
再求 h ，也是最复杂的一个：
若 a\ge c 或 b\ge c ：\
\frac{a}{c}\right\rfloor^2+(n+1)\left\lfloor
\frac{b}{c}\right\rfloor^2+n(n+1)\left\lfloor
\frac{a}{c}\right\rfloor\left\lfloor
\frac{b}{c}\right\rfloor\\&\ \ \ \ +2\left\lfloor
\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)+2\left\lfloor
\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)\\&\ \ \ \ +h(a\bmod c,b\bmod c,c,n)\end{aligned}
若 a<c 且 b<c ：\
同样地，令 m=\left\lfloor\frac{an+b}{c}\right\rfloor,t=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor 。\
将 n^2 写成 \left(2\sum\limits_{i=1}^ni\right)-n ，则：\
\begin{aligned}h(a,b,c,n)&=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2\\&=\sum\limits_{i=0}^n\left(\left(2\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j\right)-\left\lfloor\frac{ai+b}{c}\right\rfloor\right)\\&=\left(2\sum\limits_{i=0}^n\sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}j+1\right)-f(a,b,c,n)\\&=\left(2\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n(j+1)\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\right)-f(a,b,c,n)\\&=\left(2\sum\limits_{j=0}^{m-1}(j+1)\sum\limits_{i=0}^n[i>t]\right)-f(a,b,c,n)\\&=\left(2\sum\limits_{j=0}^{m-1}(j+1)(n-t)\right)-f(a,b,c,n)\\&=nm(m+1)-2f(c,c-b-1,a,m-1)\\&\ \ \ \ -2g(c,c-b-1,a,m-1)-f(a,b,c,n)\end{aligned}
于是 f,g,h 相互递归调用即可。
CRT 及 exCRT
因为 CRT 完全可以被 exCRT 代替，而 exCRT 的方法又更加有普遍性，此处只介绍 exCRT 算法。
基本算法
例题
Lucas 定理及 exLucas
Lucas 定理
当 p 为素数时，有：
\binom{n}{m}\equiv\binom{n\%p}{m\%p}\cdot\binom{n/p}{m/p}\pmod{p}
证明：
先证明两个引理：
证明 1：
易得 \binom{i}{p}=\frac{p!}{i!\cdot(p-i)!} 。
因为 p 为素数，所以分子中的 p 一定不会被分子约掉，则 \binom{i}{p} 为 p 的倍数。
证明 2：
把 (1+x)^p 二项式展开，得：
(1+x)^p=\sum\limits_{i=0}^{p}\binom{p}{i}x^i
当 i=1\sim p-1 时，又引理 1 可得 \binom{p}{i}\equiv 0\pmod{p} 。
则 (1+x)^p\equiv 1+x^p\pmod{p} 。
现在来证明原定理。
首先，对于 (1+x)^n ，\binom{n}{m} 就是其指数为 x^m 项的系数。
化简 (1+x)^n 得：
(1+x)^n=(1+x)^{p\cdot(n/p)}\cdot (1+x)^{n\%p}
\equiv (1+x^p)^{n/p}\cdot(1+x)^{n\%p}\pmod{p}
显然，左半部分只能提供 x^{kp} 项，右半部分只能提供 x 的小于 p 次方项，则要求 x^m 系数，左半部分提供 x^{p\cdot(n/p)} 的系数，即 \binom{n/p}{m/p} ，右半部分提供 x^{n\%p} 的系数，即 \binom{n\%p}{m\%p} ，而原本 x^m 系数为 \binom{n}{m} ，则得到：
\binom{n}{m}\equiv\binom{n\%p}{m\%p}\cdot\binom{n/p}{m/p}\pmod{p}
例题
Lucas 定理在处理模数 p 较小时的组合数求值问题上非常有用。
古代猪文
求 G^{\sum\limits_{d\mid n}\binom{n}{d}}\bmod 999911659 。
sol:
使用费马小定理转化为 \sum\limits_{d\mid n}\binom{n}{d}\bmod 999911658 。
可以枚举 d ，然后直接 Lucas 定理求 \binom{n}{d} ，但是这里模数过大，而 Lucas 定理复杂度依赖模数，所以会有问题。
现在我们需要缩小模数，显然可以对 999911658 分解质因数，然后 CRT 合并即可。
超能粒子炮·改
求 \sum\limits_{i=0}^k\binom{n}{i}\bmod 2333 。
sol:
因为模数很小，我们可以考虑 Lucas 定理。显然可以把式子拆成 \sum\limits_{i=0}^k\binom{n/p}{i/p}\binom{n\%p}{i\%p} 。
我们发现 i\%p 是有循环节的，稍微化一下式子：\binom{n/p}{0}\sum\limits_{i=0}^{p-1}\binom{n\%p}{i}+\binom{n/p}{1}\sum\limits_{i=0}^{p-1}\binom{n\%p}{i}+\cdots+\binom{n/p}{k/p}\sum\limits_{i=0}^{k\%p}\binom{n\%p}{i} 。把循环节提出来，就变成了 \sum\limits_{i=0}^{p-1}\binom{n\%p}{i}\times\left(\binom{n/p}{0}+\binom{n/p}{1}+\cdots+\binom{n/p}{k/p-1}\right)+\binom{n/p}{k/p}\sum\limits_{i=0}^{k\%p}\binom{n\%p}{i} 。
显然 \binom{n/p}{0}+\binom{n/p}{1}+\cdots+\binom{n/p}{k/p-1} 是一个规模更小的子问题，可以递归处理。而 \sum\limits_{i=0}^{p-1}\binom{n\%p}{i} 可以简单预处理解决。
分析一下复杂度，递归之后 n 和 k 都除以了 p ，显然递归次数是 \log_p n 级别的，可以接受。
exLucas 算法
其实它和 Lucas 定理没有一点关系，只是用途都是求组合数，所以冠上了一样的名字。不如说它是一种处理做除法时没有逆元的情况的普遍策略。
考虑一种直接一点的方法，在求组合数 \binom{n}{m}\bmod p 时，我们使用定义式 \frac{n!}{m!(n-m)!} 。但是很显然有问题：分母很有可能没有逆元（因为不与 p 互质）。exLucas 提供了一种解决此类问题的方法。
我们先把 p 分解质因数方便处理，假设分解为了若干个 p_i^k 的乘积，我们求出每个 \binom{n}{m}\bmod p_i^k ，然后 CRT 合并即可。现在需要对于任意一个质数 P ，求 \binom{n}{m}\bmod P^k 。
我们发现，因为 P 是质数，所以分母和 P 如果不互质，一定就是 P 的倍数。于是我们可以先把分母、分子中的 P 除掉，在分式外面乘即可解决没有逆元的问题。也就是把原式化为：
\frac{\frac{n!}{P^x}}{\frac{m!}{P^y}\frac{(n-m)!}{P^z}}\cdot P^{x-y-z}\bmod P^k
其中 x,y,z 都表示各个阶乘中含有的最多的 P 次数。这样分母就一定有逆元了，我们只需求出分母即可。
现在我们需要求：\frac{n!}{P^x}\bmod P^k 。显然，我们可以先把 n! 中的 P 提出来，也就是 n!=(P\cdot 2P\cdot 3P\dots)(1\cdot 2\dots) ，它等于 P^{\lfloor\frac{n}{P}\rfloor}(\lfloor\frac{n}{P}\rfloor)! 再乘上除 P 倍数之外的余项。于是我们可以递归处理 (\lfloor\frac{n}{P}\rfloor)! 。如何计算余项呢？显然余项模 P^k 后是会循环的，而 P^k 并不大，那么我们可以算出每个循环节的乘积再计算次方即可，注意可能有一些循环没满的需要乘上。
另外有一个点，我们需要计算阶乘中包含 P 的次数 x,y,z 。这很简单，仿照上面求 \frac{n!}{P^x} 的方法递归计算即可。
于是我们成功求出了 \binom{n}{m}\bmod p 。
例题
最大团
称一个无向图满足条件，当且仅当该图的任意一个连通块拥有相同的点数且都是完全图。
现有 m 种颜色和所有满足条件的含有 n 个点且节点有标号的图。我们需要将每个图都染上一种颜色，两个不同的图可以染相同颜色，求方案数。
sol:
设有 k 个图满足条件，显然最终答案是 m^k 。于是我们只需要求出满足条件的图个数即可。
我们枚举 n 的因数 d 表示每个连通块的点个数，现在就需要把 n 个点分成 n\over d 个无序的组。如果有序，答案是 \frac{n!}{(d!)^{n\over d}} ，无序只需要多除一个 ({n\over d})! ，也就是 \frac{n!}{(d!)^{n\over d}({n\over d})!} 。于是答案为：
m^{\sum\limits_{d\mid n}\frac{n!}{(d!)^{n\over d}({n\over d})!}}\bmod (10^9-401)
使用费马小定理转化为求 \sum\limits_{d\mid n}\frac{n!}{(d!)^{n\over d}({n\over d})!}\bmod(10^9-402) 。因为 10^9-402=2\times 13\times 5281\times 7283 ，所以可以分别算出对四个质数取模后的答案再 CRT 合并即可。
现在需要求答案取模一个质数的结果，我们直接枚举 d ，然后对于每个 d 使用 exLucas 的方法（把每个阶乘对 P 取模）即可。
欧拉定理
基本欧拉定理
若 \gcd(a,p)=1 ，则：
a^c\equiv a^{c\bmod \varphi(p)}\pmod p
注：费马小定理即欧拉定理在 p 为质数时的特殊情况。
扩展欧拉定理
a^c\equiv\begin{cases}a^{c\bmod \varphi(p)}&\gcd(a,m)=1\\a^c&\gcd(a,m)\ne1\land c<\varphi(p)\\a^{c\bmod\varphi(p)+\varphi(p)}&\gcd(a,m)\ne1\land c\geqslant\varphi(p)\end{cases}\pmod p
例题
LOJ525
给定 k ，求出一个次数不超过 2k ，最高次项非 0 的多项式 f(x) ，使得 \forall i\in[0,k−1],f(i)\bmod k=0 。
sol:
根据扩展欧拉定理，x^{\varphi(p)}\equiv x^{2\varphi(p)}\pmod p 。
构造多项式 x^{2\varphi(p)}-x^{\varphi(p)} 即可。
相逢是问候
给定长为 n 的初始序列 a ，以及常数 c,p 。m 次操作：
sol:
记 f(a,k,p) 表示 a 经过 k 次 a=c^a 后 \bmod\ p 的值，可以递归处理。
因为 \varphi(\varphi(\cdots\varphi(p))) 至多经过 O(\log p) 层就会变成 1 ，所以这个值在 k>2\log p 时是不变的。
所以对于没有操作 2\log p 次的位置暴力修改，线段树维护：区间和，这个区间是否所有位置都修改过超过 2\log p 次询问。
复杂度 O(n\log^2 p) 。
筛法
积性函数
常见的积性函数有：
单位函数：\epsilon(n)=[n=1] 。
恒等函数：\operatorname{id}_k(n)=n^k ，当 k=1 时，简记为 \operatorname{id}(n)=n 。
常数函数：\mathbf{1}(n)=1 。
除数函数：\sigma_k(n)=\sum\limits_{d\mid n}d^k 。\sigma_0(n) 即因数个数，记为 d(n) 。\sigma_1(n) 即因数之和，记为 \sigma(n) 。
欧拉函数：\varphi(n)=\sum\limits_{d=1}^n[\gcd(d,n)=1] 。
莫比乌斯函数：
\mu(x)=\begin{cases}1&x=1\\(-1)^k&x\ 没有平方数因子，且\ x\ 的质因子个数为 k\\0&x\ 有平方数因子\end{cases}
数论分块
用于处理 \sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor 类型的和式。
常规做法是 O(n) 的。我们发现，\left\lfloor\frac{n}{i}\right\rfloor 有很多取值是相等的，考虑使用这点来优化。
重要的性质
**证明：**
对于 $i\in[1,\sqrt n]$，取值最多 $\sqrt n$ 个；对于 $i\in[\sqrt n,n]$，$\left\lfloor\frac{n}{i}\right\rfloor\le\sqrt n$，取值最多 $\sqrt n$ 个。
于是我们可以枚举每一个 \left\lfloor\frac{n}{i}\right\rfloor 取值相等的段计算，降低复杂度。
现在的问题是，我们需要对于一个 i ，求出满足 \left\lfloor\frac{n}{j}\right\rfloor=\left\lfloor\frac{n}{i}\right\rfloor 的最大的 j 是多少，根据数学推导，容易得出 j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor 。
于是我们在 O(\sqrt n) 的复杂度内解决了问题。
狄利克雷卷积
设 f(n),g(n) 是两个数论函数，则其狄利克雷卷积为 t=f\ast g ，满足：
t(n)=\sum\limits_{d|n}f(n)g\left(\frac{n}{d}\right)
一些性质
1.
\sum\limits_{d\mid n}\mu(d)=[n=1]\Leftrightarrow\mu\ast\mathbf{1}=\epsilon
证明：
设 n=\prod p_i^{k_i},n'=\prod p_i ，n 的质因数个数为 m 。
\sum\limits_{d\mid n}\mu(d)=\sum\limits_{d\mid n'}\mu(d)=\sum\limits_{i=0}^m\binom{m}{i}(-1)^i=(1-1)^m
当且仅当 m=0 即 n=1 时 \sum\limits_{d\mid d}\mu(d)=1 。
2.
\sum\limits_{d\mid n}\varphi(d)=n\Leftrightarrow\varphi\ast\mathbf{1}=\operatorname{id}
证明：
因为 \varphi 是积性函数，只需要证明 n=p^k （p 为质数）的时候 \sum\limits_{d\mid n}\varphi(d)=n 成立即可。
\sum\limits_{i=0}^k\varphi(p^i)=1+\sum\limits_{i=1}^k(p-1)p^{i-1}=p^k
则命题得证。
点乘
定义点乘运算，对于两函数 A,B ，其点乘 A\cdot B 为一个新的函数，满足 (A\cdot B)(n)=A(n)B(n) 。
当 C 是完全积性函数时，有 (A\cdot C)\ast(B\cdot C)=(A\ast B)\cdot C 。
下面是一些常见的基本和组：
杜教筛
对于数论函数 f ，杜教筛可以在低于线性时间的复杂度内计算 S(n)=\sum\limits_{i=1}^nf(i) 。
我们找一个积性函数 g ，考虑其与 f 的狄利克雷卷积：
\begin{aligned}\sum\limits_{i=1}^n(f\ast g)(i)&=\sum\limits_{i=1}^n\sum\limits_{d\mid i}g(d)f\left(\frac{i}{d}\right)\\&=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)\\&=\sum\limits_{d=1}^ng(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\end{aligned}
$$\sum\limits_{i=1}^n(f\ast g)(i)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
令 $f\ast g=h$，则：
$$g(1)S(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
如果 $h$ 的前缀和是好求的，$g$ 的前缀和也是好求的，那么使用数论分块就可以递归快速求出 $S(n)$。
**时间复杂度**
若计算 $h$ 和 $g$ 的前缀和的时间复杂度均为 $O(1)$，则杜教筛复杂度为 $O(n^{\frac{3}{4}})$。
还可以优化：我们预处理出一部分 $S(1)\sim S(m)$ 再计算。取 $m=n^{\frac{2}{3}}$ 时，复杂度为 $O(n^{\frac{2}{3}})$。
**筛 $\mu$**
因为 $\mu\ast\mathbf{1}=\epsilon$，带入式子得：
$$\mathbf{1}(1)S(n)=\sum_{i=1}^n\epsilon(i)-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
即：
$$S(n)=1-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
$\mathbf{1}(i)$ 的前缀和就是 $i$，杜教筛即可。
**筛 $\varphi$**
因为 $\varphi\ast\mathbf{1}=\operatorname{id}$，带入式子得：
$$\mathbf{1}(1)S(n)=\sum_{i=1}^n\operatorname{id}(i)-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
即：
$$S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
$\mathbf{1}(i)$ 的前缀和是 $i$，同样杜教筛即可。
### Powerful Number 筛
定义：对于正整数 $n$，记 $n$ 的质因数分解为 $n=\prod\limits_{i=1}^mp_i^{e_i}$。$n$ 是 **Powerful Number**（简称 PN）当且仅当 $\forall 1\le i\le m,e_i>1$。
##### PN 的一些性质
1. 所有 PN 都可以表示成 $a^2b^3$ 的形式。
**证明：**
若 $e^i$ 是偶数，则将 $p_i^{e_i}$ 合并进 $a^2$ 里；若 $e_i$ 为奇数，则先将 $p_i^3$ 合并进 $b^3$ 里，再将 $p_i^{e_i−3}$ 合并进 $a^2$ 里。
2. **$n$ 以内的 PN 有 $O(\sqrt n)$ 个。**
**证明：**
考虑枚举 $a$，再考虑满足条件的 $b$ 的个数，有 PN 的个数约等于：
$$\int_1^{\sqrt n}\sqrt[3]{\frac{n}{x^2}}\mathbf{d}x=O(\sqrt n)$$
**PN 的求法**
实际上很简单。线性筛找出 $\sqrt n$ 内的所有素数，再 DFS 搜索各素数的指数即可。
由于 $n$ 以内的 PN 至多有 $O(\sqrt n)$ 个，所以至多搜索 $O(\sqrt n)$ 次。
**PN 筛**
假设现在要求积性函数 $f$ 的前缀和 $F(n)=\sum\limits_{i=1}^nf(i)$。
我们构造出一个易求前缀和的积性函数 $g$，且对于任意素数 $p$，有 $g(p)=f(p)$。记 $G(n)=\sum\limits_{i=1}^ng(i)$。
接着，构造函数 $h$ 使得 $f=g\ast h$。根据狄利克雷卷积的性质可知 $h$ 也为积性函数，因此 $h(1)=1$。
对于素数 $p$，有 $f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)$，于是可知 $h(p)=0$。又因为 $h$ 是积性函数，所以对于任意非 PN 的数 $n$ 有 $h(n)=0$，即 $h$ 仅在 PN 处取有效值。
现在，根据 $f=g\ast h$ 有：
$\begin{aligned}F(n)&=\sum\limits_{i=1}^nf(i)\\&=\sum\limits_{i=1}^n\sum\limits_{d\mid i}h(d)g\left(\frac{i}{d}\right)\\&=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}h(d)g(i)\\&=\sum\limits_{d=1}^nh(d)G\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\\&=\sum\limits_{d=1\land d\in \operatorname{PN}}^nh(d)G\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\end{aligned}
考虑计算 $h(p^c)$，两种方法：
- 推出 $h(p^c)$ 仅与 $p,c$ 有关的公式，直接计算。
- 根据 $f=g\ast h$ 有 $f(p^c)=\sum\limits_{i=0}^c g(p^i)h(p^{c−i})$，移项得 $h(p^c)=f(p^c)-\sum\limits_{i=1}^cg(p^i)h(p^{c−i})$，枚举素数 $p$ 和指数 $c$ 即可求出所有 $h(p^c)$。
总复杂度 $O(n\log n)$。
#### 例题
1. **Crash 的数字表格**
$T$ 组数据，给定 $n,m$，求：
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)$$
**sol:**
不妨设 $n\le m$，则：
$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{\gcd(i,j)}\\&=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{d}[\gcd(i,j)=d]\\&=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij[\gcd(i,j)=1]\\&=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum\limits_{x\mid\gcd(i,j)}\mu(x)\\&=\sum\limits_{d=1}^{n}d\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij[x\mid \gcd(i,j)]\\&=\sum\limits_{d=1}^{n}d\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{dx}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{dx}\rfloor}x^2ij\\&=\sum\limits_{d=1}^n\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}dx^2\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{dx}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{dx}\rfloor}j\end{aligned}
令 t=dx ，则原式 =\sum\limits_{t=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{t}\rfloor}j\sum\limits_{dx=t}dx^2\mu(x) 。
即是：
\sum\limits_{t=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{t}\rfloor}jt\sum\limits_{x\mid t}x\mu(x)
可以发现，t\sum\limits_{x\mid t}x\mu(x) 为积性函数，可以线性筛预处理前缀和，而前面一部分使用数论分块处理即可。
简单的数学题
给定 n ，求：
\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)
sol:
使用 \sum\limits_{d\mid n}\varphi(d)=n 。
\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\sum\limits_{x\mid i,x\mid j}\varphi(x)\\&=\sum\limits_{x=1}^n\varphi(x)\sum\limits_{i=1}^ni[x|i]\sum\limits_{j=1}^nj[x|j]\\&=\sum\limits_{x=1}^n\varphi(x)\sum\limits_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}ix\sum\limits_{j=1}^{\left\lfloor\frac{n}{x}\right\rfloor}jx\\&=\sum\limits_{x=1}^n\varphi(x)x^2\left(\sum\limits_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}i\right)^2\end{aligned}
后面可以数论分块解决，现在需要快速求出 \varphi(i)i^2 的前缀和。
考虑杜教筛，令 f=\varphi\cdot\operatorname{id}^2 ，需要找出合适的 g 。
为了 (f\ast g) 求前缀和方便，由于 i\cdot\frac{n}{i}=n ，取 g=\operatorname{id}^2 ，以消掉 i 。
(f\ast g)(n)=\sum\limits_{d\mid n}\varphi(d)d^2\cdot\left(\frac{n}{d}\right)^2=n^2\sum\limits_{d\mid n}\varphi(d)=n^3
带到式子里：
\begin{aligned}g(1)S(n)&=\sum\limits_{i=1}^n(f\ast g)(i)-\sum\limits_{i=2}^n\operatorname{id}^2(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\&=\sum\limits_{i=1}^nn^3-\sum\limits_{i=2}^nn^2S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\end{aligned}
显然，n^3 与 n^2 的前缀和都可以 O(1) 求，于是问题解决。
Min_25 筛
给定积性函数 f ，其在质数的幂次的取值为 f(p^k)=p^k(p^k-1) ，求 \sum\limits_{i=1}^nf(i) 。
sol:
这里使用 PN 筛完成此题。
易得 f(p)=p(p−1)=\operatorname{id}(p)\cdot\varphi(p) ，构造 g(n)=\operatorname{id}(n)\cdot\varphi(n) 。
我们可以使用杜教筛求 g 的前缀和。具体来说，构造 f=\operatorname{id} ，则 f\ast g=\operatorname{id}^2 。
之后计算 h(p^k) 的取值：
Stern-Brocot 树
基础定义
Stern-Brocot 树是一种维护最简分数的数据结构。
逐层构造
Stern-Brocot 树可以在迭代构造第 k 阶 Stern-Brocot 序列的过程中得到。
第 0 阶 Stern-Brocot 序列由两个分数组成：
\frac{0}{1},\ \frac{1}{0}
此处的 \frac{1}{0} 严格意义上并不算是有理分数，可以理解为表示 \infty 的最简分数。
在第 k 阶 Stern-Brocot 序列相邻的两个分数 \frac{a}{b} 和 \frac{c}{d} 中间插入 \frac{a+c}{b+d} ，就得到第 k+1 阶 Stern-Brocot 序列。
前几次迭代的结果如下：
\frac{0}{1},\ \frac{1}{1},\ \frac{1}{0}
\frac{0}{1},\ \frac{1}{2},\ \frac{1}{1},\ \frac{2}{1},\ \frac{1}{0}
\frac{0}{1},\ \frac{1}{3},\ \frac{1}{2},\ \frac{2}{3},\ \frac{1}{1},\ \frac{3}{2},\ \frac{2}{1},\ \frac{3}{1},\ \frac{1}{0}
将每次迭代中新添加的分数连结成树状结构，就得到了 Stern-Brocot 树。如下图所示（图片来自 OI-wiki）：
三元组构造
另一种等价的构造方式是以三元组 (\frac{0}{1},\frac{1}{1},\frac{1}{0}) 作为根节点，且在每个节点 (\frac{a}{b},\frac{p}{q},\frac{c}{d}) 后都分别添加 (\frac{a}{b},\frac{a+p}{b+q},\frac{p}{q}),\ (\frac{p}{q},\frac{p+c}{q+d},\frac{c}{d}) 为左右子节点，就可以构造出整个 Stern-Brocot 树。
Stern-Brocot 树的每个节点记录的三元组中，实际存储的分数是位于三元组中间的分数 \frac{p}{q} ，而左右两个分数 \frac{a}{b} 和 \frac{c}{d} 是更早就出现过的分数。
性质
基本性质 ：Stern-Brocot 树是分数的二叉搜索树 ，即树上节点的中序遍历得到的分数序列是递增的。
单调性 ：Stern-Brocot 树中，每一层的分数都是单调递增 的。
最简性 ：Stern-Brocot 树构造出来的所有分数都是最简分数 。
完全性 ：Stern-Brocot 树能构造出来任意 一个正的最简分数。
这些性质的证明略去，可自行搜索。
应用
基础应用
在 Stern-Brocot 树上查找一个确定的分数 \frac{p}{q} 。
sol:
每次暴力往左或右跳的复杂度为 O(p+q) ，无法接受。
我们发现，这个方法复杂度高的原因是我们经常会连续往左或往右跳很多步。
考虑优化。观察到一次往左跳再接一次往右跳一定会让分子分母都至少变为原来的两倍，所以“拐弯”的次数是 O(\log(p+q)) 的。
于是现在我们需要快速确定每次拐弯的位置。
假设当前节点为 (\frac{a}{b},\frac{x}{y},\frac{c}{d}) ，如果 \frac{x}{y}\le\frac{p}{q} ，那么需要向右递归。设递归次数为 t ，则 \frac{x+tc}{y+td}\ge\frac{p}{q} ，解这个不等式即可。向左递归同理。
时间复杂度 O(\log(p+q)) 。
拓展应用
大部分时候，我们在树上查找的分数其实是不确定的，比如我们需要根据当前分数的值跑一个二分查找的检验算法来决定具体是往左走还是往右走。
这个时候，把刚才通过解方程来确定次数的部分改为二分连续向左或向右的次数 t 即可。复杂度 O(\log^2(p+q)) 。
例题
Fraction
若有多解，输出 $q$ 最小的一组，若仍有多解，输出 $p$ 最小的一组。
**sol:**
Stern-Brocot 树上二分的板子，连续移动次数可以列不等式解出来，复杂度 $O(T\log a)$。
2. **Farey 序列**
求分子和分母都 $\le n$ 的最简真分数组成的序列中第 $k$ 小的数。
**sol:**
在 Stern-Brocot 树上二分，剩下的就是类似二分答案地，对于一个分数 $\frac{x}{y}$，我们需要计算 $\le\frac{x}{y}$ 的分子和分母都 $\le n$ 的最简真分数数量，这个数量为：
$\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^i[\gcd(i,j)=1]\left[\frac{j}{i}\le\frac{x}{y}\right]\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\sum\limits_{d\mid\gcd(i,j)}\mu(d)\left[\frac{j}{i}\le\frac{x}{y}\right]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^i\left[\frac{j}{i}\le\frac{x}{y}\right]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^i\left[j\le\frac{ix}{y}\right]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left\lfloor\frac{ix}{y}\right\rfloor\end{aligned}
整除分块，\mu 的前缀和用杜教筛求，预处理 O(n^{\frac{2}{3}}) ，单次询问 O(1) 。后面是类欧，对于每个 \frac{x}{y} ，需要做 O(\sqrt n) 次类欧，每次类欧 O(\log n) 。
而 Stern-Brocot 树上二分复杂度为 O(\log^2 n) ，所以总复杂度 O(n^{\frac{2}{3}}+\sqrt{n}\log^3n) 。
原根
阶及其性质
定义
我们把满足 a^x\equiv 1\pmod{m} 的最小正整数 x 称为 a 模 m 的阶，记作 \delta_m(a) 。
显然 a\perp m 是 \delta_m(a) 存在的充要条件，于是下面假设 a\perp m 。
性质
证明：
使用反证法，假设 1\le x<y<\delta_m(a) ，且 a^x\equiv a^y\pmod{m} 。
那么 a^{y-x}\equiv 1\pmod{m} ，而 y-x<\delta_m(a) ，说明 \delta_m(a) 不是最小循环节，矛盾。
证明：
感性理解：x 是 \delta_m(a) 的整数倍，说明 a 的次方跳了整数个循环，模 m 一定还是 1 。
证明：
考虑一个数自身相乘时，它的阶如何变化。如果我们将模 m 下 a 的幂次看成一个长为 \delta_m(a) 的环，那么 a 的幂次相当于在环上每次跳一步，a^k 的幂次相当于在环上每次跳 k 步。手模一下即可。
求法
显然，如果 x 为 \delta_m(a) 的倍数，那么必然有 a^x\equiv 1\pmod{m} 。
因为阶都是 \varphi(m) 的因数，于是考虑令 t=\varphi(m) ，枚举 \varphi(m) 的因数 p ，用 t 不断试除 p 直到 t 不整除 p 或者 a^{\frac{t}{p}}\not\equiv 1\pmod{m} 。
最后剩下的 t 就是得到的阶。
原根
定义
若 \delta_m(a)=\varphi(m) ，则称 a 为模 m 的原根。并不是所有数都有原根。
原根有什么用呢？它有一个性质：原根的若干次幂在模 m 意义下取遍了所有与 m 互质的数。这使得我们在考虑解与模数互质且模数存在原根的同余方程时可以用原根的若干次幂代替未知数，在求解高次剩余时非常有用。具体后面有例题。
性质
原根判定定理
>**证明：**
>
>还是用反证法。假设存在一个 $k$，使得它满足上面的条件，却不是 $m$ 的原根。
>
>于是，$k$ 的阶应满足 $\delta_m(k)<\varphi(m)$ 且 $\delta_m(k)\mid\varphi(m)$，所以存在 $\varphi(m)$ 的质因子 $p$ 满足 $\delta_m(k)\mid\frac{\varphi(m)}{p}$。
>
>而根据阶的性质 $a^{\delta_m(k)}\equiv 1\pmod{m}$，于是 $a^{\frac{\varphi(m)}{p}}\equiv a^{\delta_m(k)}\equiv 1\pmod{m}$，矛盾。
2. **原根存在定理**
$m$ 有原根当且仅当 $m=2,4,p^a,2p^a$，其中 $p$ 是奇质数。
3. **原根个数定理**
若正整数 $m$ 有原根，则原根个数为 $\varphi(\varphi(m))$。
4. **最小原根的范围**
任何有原根的数，最小原根一定不超过 $O(m^{0.25})$ 数量级。
#### 求法
根据原根判定定理和最小原根的范围，我们可以预处理每个数的最小质因子后 $O(m^{0.25}w(m)\log m)$ 求出某数的最小原根，从而求出它的所有原根。
#### 例题
1. **小 A 与两位神仙**
给定正整数 $m$，保证 $m$ 是一个奇质数的正整数次幂。$n$ 次询问，每次给定正整数 $x,y$，保证 $x$ 与 $m$ 互质，$y$ 与 $m$ 互质，求是否存在非负整数 $a$ 使得 $x^a\equiv y\pmod{m}$。
**sol:**
根据题目条件，$m$ 存在原根 $g$。因为 $x$ 与 $m$ 互质，而 $g$ 的次方刚好可以取到所有与 $m$ 互质的数，所以必然存在 $g^{X}\equiv x\pmod{m}$。同理设 $g^{Y}\equiv x\pmod{m}$。
所以式子变为 $g^{Xa}\equiv g^{Y}\pmod{m}$，所以 $Xa\equiv Y\pmod{\varphi(m)}$。根据裴蜀定理，它有解当且仅当 $\gcd(X,\varphi(m))\mid Y$，这等价于 $\gcd(X,\varphi(m))\mid\gcd(Y,\varphi(m))$。
又因为 $\delta_m(x)=\frac{\delta_m(g)}{\gcd(\delta_m(g),X)}$，所以条件又等价于 $\delta_m(y)\mid\delta_m(x)$。直接使用上面的方法求阶即可。需要使用 Pollard-Rho。