数论

· · 算法·理论

\text{BSGS}、原根、阶

阶

定义

若 a^x\equiv 1\pmod p，且 x 最小，则称 x 为 a 在模 p 意义下的阶，记作 \delta_p(a)。

容易发现，仅当 \gcd(x,p)=1 时，阶存在，可用扩欧证明。

性质

原根

如果 \delta_p(g)=\varphi(p)，那么 g 称为 p 的原根。

性质

对于 0<i\le \varphi(p)，g^i\bmod p 两两不同，即构成 p 的简化剩余系。

设 f(x) 满足 g^{f(x)}\equiv x\pmod p，则有 xy\equiv g^{f(x)}g^{f(y)}\equiv g^{f(x)+f(y)}\pmod p，于是便将乘法转换成加法。

判定定理

如果 p\ge 3，且 \gcd(g,p)=1，那么 g 是 p 的原根当且仅当 \sum\limits_{d|\varphi(p),d\in P}[g^\frac{\varphi(p)}{d}\equiv 1]=0，其中 P 为质数集。不会证。

原根个数

如果 p 有原根，那么个数为 \varphi(\varphi(p))。

假如说 g 是 p 的原根，即 \delta_p(g)=\varphi(p)，那么根据阶的第二条性质可得 \delta_p(g^k)=\cfrac{\varphi(p)}{\gcd(k,\varphi(p))}，显然只有当 \gcd(k,\varphi(p))=1 时，g^k 是原根，所以证毕。

存在定理

当且仅当 p\in\{2,4,x^k,2x^k|x\in P,x\ne 2,k\in N^*\} 时 p 存在原根。不会证。

最小原根

大概是 n^{0.25}，反正不会 T。不会证。

\text{BSGS}

基本形式

求满足 a^x\equiv b\pmod p 的最小整数 x。其中 a,p 互质。

\text{BSGS}

由于互质，所以 0\le x<\varphi(p)，所以令 s=\lceil \sqrt p\rceil，然后便可以转换为 a^{ks-r}\equiv b\pmod p。然后又因为 a 存在逆元，所以 a^{ks}\equiv ba^r\pmod p。

注意到 1\le k\le s，0\le r\le s，所以直接用哈希表预处理一边，另一边枚举即可。时间复杂度 O(\sqrt p)，不是多项式时间复杂度。

其他例子

求满足 x^a\equiv b\pmod p 最小 x。其中 p 是质数。

因为 p 是质数，所以存在原根。先求出最小原根 g，那么根据原根的性质将 x 表示为 g^{x'}，b 表示为 g^{b'}，所以有 g^{x'a}\equiv g^{b'}\pmod p，根据扩展欧拉定理，即 x'a \equiv b'\pmod{\varphi(p)}。

如果 x_0 为该方程的特解，根据不定方程解的表达形式，那么有 x'\equiv x_0+t\frac{\varphi(p)}{\gcd(\varphi(p),a)}\pmod{\varphi(p)}，所以解的个数即为 \gcd(\varphi(p),a) 个。

处理范围

只要满足可逆性，便可以求解，包括矩阵。即 A^x\equiv B\pmod p。

如果只是求 a^x\equiv 1\pmod p，请不要采用 \text{BSGS}，求阶比这更快。

\text{exBSGS}

处理 a,p 不互质时。

很好办，令 D 为 \gcd(a,p)，如果 D\ne 1，那么即 \frac{a}{D}a^{x-1}\equiv\frac{b}{D}\pmod{\frac{p}{D}}，如果 D 不整除 b，那么无解。然后不断重复该过程，直到 D=1。

令 d 为所有 D 的乘积，k 为重复次数。则 \frac{a^k}{d}a^{x-k}\equiv \frac{b}{d}\pmod{\frac{p}{d}}。然后即为一般式。需要特判 x<k 的情况。

\text{Miller Rabin}、\text{Pollard Rho}

\text{Miller Rabin}

试判断 q 是否为质数。其中 q\in [1,10^{18}]。

试除法

### 费马素性测试 费马小定理：如果 $p$ 为质数，那么对于 $a$，如果满足 $\gcd(a,p)=1$，那么 $a^{p-1}\equiv 1\pmod p$。 根据这个，如果对于 $a\in [2,q-1]$，有 $a^{q-1}\not\equiv 1\pmod q$，那么一定可以说明 $q$ 不是素数。 但是，‌对于一类合数卡迈克尔数，可以通过如上测试。 ### 二次探测定理 如果 $p$ 为奇质数，那么 $x^2\equiv 1\pmod p$ 只有两个解 $1$ 和 $p-1$。 于是如果 $q=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$，用 crt 可以求得所有的解。显然只有当 $k=1$ 即 $q=p^r$ 时才会通过该测试。 ### $\text{Miller Rabin}

对于卡迈克尔数有一个性质，一定包含三个互不相同的质因子，所以不满足二次探测定理。

于是便可以二者相结合进行判断。

令 q-1=k2^{u}。

一共进行 t 轮，每轮从 [2,q-1] 随机出一个底数 a。令 x=a^{k}\bmod q，如果 x=1 直接通过该轮测试。否则将 x 不断平方 u 次，如果某一次 x=1 且前一次 x=q-1，那么也可以通过该轮测试，否则则表示 q 有非平凡根，不满足二次探测定理，即 q 不是质数。

一般在 long long 范围内，t 取 10 便不会出错。

\text{Pollard Rho}

若 q 是合数，试找出 q 的一个非平凡因子（\ne 1 或 q）。q\in [2,10^{18}]。

试除法

生日悖论

如果在 [1,n] 范围内随机生成一个数，那么第一次出现重复的数列长度近似为 O(\sqrt n)。

\text{Pollard Rho}

假如说 p 是 q 的最小质因子，那么期望在 [1,q] 里随机 O(\sqrt p) 个数，便有两个数模 p 同余。时间复杂度大致为 O(q^{\frac{1}{4}})。

如果 x\equiv y\pmod p，那么 p\mid \gcd(|x-y|,q)，所以 \gcd(|x-y|,q) 便是 q 的一个非平凡因子。但是两两作差时间复杂度会重新恢复至 O(\sqrt q)。

考虑一个随机数生成器 f(x)=(x^2+c)\bmod n。用这个构造数列，由于是 \rho 型，发现如果 x\equiv y\pmod p，那么 f(x)\equiv f(y)\pmod p。

Floyd 判环

令 x=f(0),y=f(x)。

每一次 x=f(x),y=f(f(y))，发现 x,y 间距离不断增加，那么当 x=y 时可以直接终止。过程中判断即可。

优化

于是便可以把 |x-y| 不断累乘，最后判断即可。但是需要跑满，所有考虑倍增，每 2^{k} 次后判断一次，实验证明，每 \min(2^k,128) 次判断比较快。

二次剩余

若 a 满足存在 x 使得 x^2\equiv a\pmod p，且 \gcd(a,p)=1，则称 a 为模 p 意义下的二次剩余。n 次剩余也这么定义。

数论方面的东西就不说了。下文讨论 p 为奇质数的情况。

Legendre 符号

\left(\frac{a}{p}\right)=\begin{cases} 0 & p\mid a,\\ 1 & a\ 是\ p\ 的二次剩余\\ -1 & 不是\\ \end{cases}

Euler 判别法

\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p

证明：

令 g 为 p 的原根。若 x^2\equiv a\pmod p，则

g^{2x'}\equiv g^{a'}\pmod p\Rightarrow 2x'\equiv a'\pmod{p-1}\Rightarrow 2\mid a'

然后因为

a^{\frac{p-1}{2}}\equiv (g^{a'})^{\frac{p-1}{2}}\equiv (g^{\frac{p-1}{2}})^{a'}\equiv (-1)^{a'}\pmod p

所以如果 a 是 p 的二次剩余，则 2\mid a'，该式 =1，否则 =-1。

推论

其中 p,q 为奇素数，为什么呢？读者用 Gauss 引理自证不难。

Cipolla 求解

求出 x^2\equiv a\pmod p 的所有 x。

仅讨论 p 为奇素数的情况。首先 Euler 判别是否有解。

然后找到 b(1\le b\le p)，使得 b^2-a 为模 p 的非二次剩余。即 (b^2-a)^{\frac{p-1}{2}}\equiv -1\pmod p。根据推论 2，期望随机到 b 的概率为 \frac{1}{2}。

设 \omega =\sqrt{b^2-a}，计算 x_1\equiv (b+\omega)^{\color{red}\frac{p+1}{2}}\pmod p，x_2\equiv p-x_1\pmod p。

这里的 \omega 类似于虚数单位 i，将原来 p 的完全剩余系 \Z_p 扩展为 \Z_p[\omega]。在这个扩域中，每一个数都可以表示为 x+y\omega(x,y\in \Z_p)。前面是实部，后面是虚部。

其中加减乘除都类似于 i，(x_1+y_1\omega)(x_2+y_2\omega)=(x_1x_2+y_1y_2\omega^2)+(x_1y_2+x_2y_1)\omega。

证明一

为何 x_1^2\equiv a\pmod p。

\begin{aligned} x_1^2&=(b+\omega)^{p+1}\\ &=(b+\omega)^p(b+\omega)\\ &=(b^p+\omega^p)(b+\omega)\ \ 二项式定理\\ &=(b-\omega)(b+\omega) \end{aligned}

由费马小定理可得 b^p\equiv b\pmod p，然后 \omega^p\equiv \omega(\omega^2)^{\frac{p-1}{2}}\pmod p，因为 \omega^2=b^2-a 不是二次剩余，故 (\omega^2)^{\frac{p-1}{2}}\equiv -1\pmod p。

证明二

因为 $x_1^2=(x^2+y^2\omega^2)+(2xy)\omega=a$。其中 $a\in \Z_p$，则 $2xy\equiv 0\pmod p$。 若 $x=0$，则 $y^2\omega^2=a$。因为 $\omega^2$ 非二次剩余，所以根据推论一有 $y^2$ 非二次剩余，但是 $y\in \Z_p$，故 $y^2$ 一定二次剩余，矛盾。 ## 一般情况 按照套路，将 $p$ 分解为 $p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$。分 $2^k$ 和 $p^k$ 讨论然后 crt 合并。挂个简略版。 ### $2^k $k\ge 3$，则 $a\equiv 1\pmod 8$，始终 $4$ 个解，从 $k=3$ 递推，$x_0$ 为已知答案。则 $x_1\equiv x_0$ 或 $x_1\equiv x_0+2^k$，其中 $2$ 个无解。 ### $p^k

等价于 p 的情况。

斐波那契与循环节

求斐波那契 \bmod 10^9+9 最早出现 x 的位置。

根据通项公式

f_n=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right]

设 f_n=\frac{1}{\sqrt 5}(a^n-b^n)，注意到 5 是二次剩余，所以前面是常数；观察到 ab=-1，所以处理 a^n-(\frac{-1}{a})^n。

然后分奇偶讨论，如果是偶数，则 x-\frac{1}{x}\equiv b\pmod p，解一元二次方程，然后用 bsgs 求解即可。

求模 p 意义下的最小循环节。一下只考虑 p 为素数的情况。如果 p 不是素数，容易发现循环节长度不超过 6p。

需要特判的 p=2 时，答案为 3。p=5 时，答案为 20。

### $5$ 是 $p$ 的二次剩余 那么 $5^{\frac{p-1}{2}}\equiv 1\pmod p$，令 $\phi =\frac{1+\sqrt 5}{2}$，$\bar{\phi}=\frac{1-\sqrt 5}{2}$。 容易发现 $$ \begin{aligned} \phi^p&= \frac{(1+\sqrt 5)^p}{2^p}\\ &= \frac{1^p+\sqrt 5^p}{2}\ \ 二项式定理/费马小定理\\ &= \frac{1+\sqrt 5\sqrt 5^{p-1}}{2}\\ &= \frac{1+\sqrt 5}{2}\ \ (\sqrt5^{p-1}= 5^{\frac{p-1}{2}}= 1) \end{aligned} $$ $\bar{\phi}$ 同理。 所以 $p-1$ 是一个周期。最小周期是它的因数。 ### $5$ 不是 $p$ 的二次剩余 那么 $5^{\frac{p-1}{2}}\equiv -1\pmod p$。 根据上述推导容易发现 $\phi^p=\frac{1-\sqrt 5}{2}=\bar{\phi}$。同理 $\bar{\phi}^p=\phi$。 于是，$\phi^{2p+3}=(\phi^{p+1})^2\phi=(\bar{\phi}\phi)^2\phi$。注意到 $\phi\bar{\phi}=-1$。所以原式 $=\phi$。 $\bar{\phi}$ 同理。于是 $2p+2$ 是一个周期。 # 数论函数、莫比乌斯反演、亚线性筛法 ## 数论函数 ### 狄利克雷卷积 $$ (f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) $$ 枚举倍数可做到 $O(n\log n)$。满足交换律、结合律，对加法的分配律。 --- 求 $h=f*g$，其中 $f$ 和 $g$ 均为积性函数。 显然 $h$ 也为积性函数，可以通过求出 $h$ 在 $p^k(k>1)$ 处的点值求出 $h$，时间复杂度为 $O(\frac{\sqrt n}{\log n}\log^2 n)=O(\sqrt n\log n)$ 加线性筛时间复杂度 $O(n)$。 --- 如果 $C$ 是**完全**积性函数，则有 $(A\cdot C)*(B\cdot C)=(A*B)\cdot C$。 ### 狄利克雷前缀和 $g(n)=1(n)=1$，用高维前缀和枚举质数可以做到 $O(n\log \log n)$，后缀和同理。 ### 积性函数 对于 $a\perp b$ 满足 $f(ab)=f(a)f(b)$ 的函数称为积性函数，$\forall a,b$ 称为完全积性函数。如果 $f$ 和 $g$ 是积性函数，那么 $h=f*g$ 也是积性函数。 - 单位函数 $\varepsilon(n)=[n=1]$。 - 常数函数 $1(n)=1$。 - 恒等函数 $id(n)=n$。 如果 $f*g=\varepsilon$，则称 $f$ 为 $g$ 的逆元，也即 $g^{-1}$。$g$ 可逆的充要条件为 $g(1)\ne 0$。 $$ \mu \xrightleftharpoons[*\mu]{*1}\varepsilon\xrightleftharpoons[*\mu]{*1}1\xrightleftharpoons[*\mu]{*1}d\\ \varphi\xrightleftharpoons[*\mu]{*1}id\xrightleftharpoons[*\mu]{*1}\sigma $$ 由莫反可得。 ### 莫比乌斯函数 $$ \mu(n)=\left\{\begin{matrix} 1 & i=1\\ (-1)^{k} & n=\prod_{i=1}^{k}p_i\\ 0 & \text{otherwise} \end{matrix}\right. $$ ## 莫比乌斯反演 若 $F=f*1$，则 $f=F*\mu$。 只需证明 $\mu *1=\varepsilon$，即证明 $$ [n=1]=\sum_{d|n}\mu(d) $$ 由于 $\mu(d)=0$ 的因子无贡献，所以只需考虑若干质因子的乘积。$n=1$ 显然成立。如果 $n\ne 1$，令 $k$ 为因子数。 $$ \sum_{d|n}\mu(d)=\sum_{i=0}^k\binom{k}{i}(-1)^i=(-1+1)^k=0 $$ 欧拉反演：$n=\sum_{d|n}\limits\varphi(d)$。 ### 形式化 $$ F(n)=\sum_{d|n}f(d)\Longleftrightarrow f(n)=\sum_{d|n}F(d)\mu(\frac{n}{d})\\ F(n)=\sum_{n|d}f(d)\Longleftrightarrow f(n)=\sum_{n|d}F(d)\mu(\frac{d}{n})\\ \varepsilon(n)=[n=1]=\sum_{d|n}\mu(d) $$ 常常可以用来容斥，比如对于二式 $f(n)$ 表示值恰好为 $n$ 的函数值，$F(n)$ 表示满足值为 $n$ 的倍数的函数值的和。 ### 常见结论 $$ \mu(ij)=\mu(i)\mu(j)[\gcd(i,j)=1]\\ \varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\ \sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor=\sum_{i=1}^{n}d(i)\\ d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\\ \sum_{i=1}^x[i\perp x]i=\frac{x\varphi(x)}{2}\\ \sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j))=\sum_{d=1}f(d)\sum_{e=1}^{\lfloor \frac{n}{d}\rfloor}\mu(e)\lfloor\frac{n}{de}\rfloor\lfloor\frac{m}{de}\rfloor=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}f(d)\mu(\frac{T}{d}) $$ 如何证明？ 对于第三个，考虑建立倍数与约数的双射。 对于第四个，读者自证不难。 对于第五个，如果 $i\perp x$，根据辗转相除法可得 $x-i\perp x$，发现是成对出现。 对于第六个，等式 $1$ 整除分块套整除分块可以做到 $O(n^{\frac{3}{4}})$，等式 $2$ 可以整除分块加杜教筛做到 $O(n^{\frac{2}{3}})$。 --- $$ \def\g{\gcd} \def\s{\sum} \def\f{\frac} \begin{aligned} \s_{i=1}^{N}\s_{j=1}^{N}\text{lcm}(A_i,A_j)&=\s_{i=1}^{N}\s_{j=1}^{N}\frac{A_iA_j}{\g(A_i,A_j)}\\ &=\s_{d=1}^{M}\f{1}{d}\s_{i=1}^{N}\s_{j=1}^{N}A_iA_j[\g(A_i,A_j)=d]\\ &=\s_{d=1}^{M}\s_{e=1}^{\lfloor\f{M}{d}\rfloor}\frac{\mu(e)}{d}\s_{i=1}^{N}[de|A_i]\s_{j=1}^{N}[de|A_j]A_iA_j\\ &=\s_{T=1}^{M}\s_{d|T}\mu(d)\f{d}{T}S^2(T)\\ &=\s_{T=1}^{M}\f{S^2(T)}{T}\s_{d|T}\mu(d)d \end{aligned} $$ 其中 $M$ 为值域，$S(T)$ 可以通过高维后缀和，$\mu\cdot id$ 可以通过高维前缀和。时间复杂度 $O(M\log \log M)$。 ## 亚线性筛 求 $s(n)=\sum\limits_{i=1}^{n}f(i)$。其中 $f$ 为积性函数。 ### 杜教筛 考虑构造 $g$，使得 $h=g*f$ 且 $h$ 和 $g$ 的前缀和易求。 适用范围：$g,h$ 前缀和易求。 $$ \begin{aligned} \sum_{i=1}^{n}h(i)&=\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d})\\ &=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\ &=\sum_{d=1}^ng(d)s(\lfloor\frac{n}{d}\rfloor)\\ &=g(1)s(n)+\sum_{d=2}^ng(d)s(\lfloor\frac{n}{d}\rfloor) \end{aligned} $$ 所以有 $$ g(1)s(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)s(\lfloor\frac{n}{d}\rfloor) $$ 然后递归加记忆化，时间复杂度大概是 $O(n^{\frac{3}{4}})$，但是预处理 $\le T=O(n^{\frac{2}{3}})$ 可以做到 $O(n^\frac{2}{3})$。 --- 数列 $a$ 初始为空，每次随机加入一个 $1\sim n$ 中的数，当 $\gcd=1$ 时停止，求期望长度。 发现即求 $\sum\limits_{i=1}^{\infin}iP(len=i)$，但是这并不容易，考虑转 $\sum\limits_{i=1}^{\infin}P(len\ge i)$，然后容斥一下 $1+\sum\limits_{i=2}^{\infin}1-P(len<i)$。 此时 $P$ 就变成总序列个数 $n^{i-1}$ 中 $\gcd=1$ 的个数，推一下即 $\sum\limits_{d=1}^{n}\mu(d)\frac{\lfloor\frac{n}{d}\rfloor^{i-1}}{n^{i-1}}$，然后喜闻乐见地交换求和顺序，发现内部是等比序列求和然后便可以整除分块加杜教筛了。 --- 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(ij)$，其中 $n\le 10^5$，$m\le 10^9$。 设 $f(n,m)=\sum_{j=1}^{m}\varphi(nj)$，$s$ 为 $n$ 的所有质因数的乘积。 $$ \begin{aligned} f(n,m)&=\frac{n}{s}\sum_{j=1}^{m}\varphi(sj)\\ &=\frac{n}{s}\sum_{j=1}^{m}\frac{\varphi(s)\varphi(j)\gcd(s,j)}{\varphi(\gcd(s,j))}\\ &=\frac{n}{s}\sum_{j=1}^m\varphi(\frac{s}{\gcd(s,j)})\varphi(j)\gcd(s,j)\\ &=\frac{n}{s}\sum_{j=1}^m\varphi(\frac{s}{\gcd(s,j)})\varphi(j)\sum_{d|\gcd(s,j)}\varphi(d)\\ &=\frac{n}{s}\sum_{j=1}^m\varphi(j)\sum_{d|\gcd(s,j)}\varphi(\frac{s}{\frac{\gcd(s,j)}{d}})\\ &=\frac{n}{s}\sum_{j=1}^m\varphi(j)\sum_{d|\gcd(s,j)}\varphi(\frac{s}{d})\\ &=\frac{n}{s}\sum_{d|s}\varphi(\frac{s}{d})\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(dj) \end{aligned} $$ 后面那堆是 $f(d,\lfloor\frac{m}{d}\rfloor)$，递归子问题，注意记忆化。 --- 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}[i\perp j][j\perp k]$，其中 $n,m\le 10^9$，$k\le 2\times 10^3$。 因为 $k$ 很小，考虑处理关于 $k$ 的部分。 $$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}[i\perp j][j\perp k]&=\sum_{d|k}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor }[i\perp dj]\\ &=\sum_{d|k}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor }[i\perp j][i\perp d]\\ &=\sum_{d|k}\mu(d)\sum_{i=1}^{\lfloor \frac{m}{d}\rfloor}\sum_{j=1}^{n}[i\perp j][j\perp d] \end{aligned} $$ 注意到后面那堆是子问题，于是直接递归计算，时间复杂度由于 $k$ 的原因是可以过的。 ### Powerful Number 筛 如果 $n=\prod\limits_{i=1}^{k}p_i^{r_i}$，对于 $\forall 1\le i\le k$ 满足 $r_i>1$，则称 $n$ 为幂数（PN）。可以证明 $1\sim n$ 以内幂数的数量在 $O(\sqrt n)$ 级别。可以预处理 $\sqrt n$ 以内的质数然后 dfs 求出所有的幂数。 考虑构造积性函数 $g$，满足 - 对于质数 $p$，$g(p)=f(p)$。 - 前缀和 $G$ 易求。 - 存在积性函数 $h$ 满足 $f=g*h$，$h(p^k)$ 的值易求。 因为 $g,h$ 为积性函数，则 $g(1)=h(1)=1$。 对于质数 $p$，$f(p)=g(1)h(p)+g(p)h(1)=g(p)$，则 $h(p)=0$。于是可推得 $h$ 在非 PN 处的取值均为 $0$。所以 $$ \begin{aligned} \sum_{i=1}^{n}f(i)&=\sum_{i=1}^{n}\sum_{d|i}h(d)g(\frac{n}{d})\\ &=\sum_{d=1}^{n}h(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor }g(i)\\ &=\sum_{d=1}^{n}h(d)G(\lfloor \frac{n}{d}\rfloor) \end{aligned} $$ 由于仅当 $d$ 为 PN 时非 $0$，所以只有 $\sqrt n$ 个非 $0$。 如果 $G$ 和 $h(p^k)$ 可 $O(1)$ 求，则时间复杂度 $O(\sqrt n)$。 --- 计算 $h(p^k)$： - 直接用公式算。 - 递推。由于 $f(p^k)=\sum\limits_{i=0}^{k}g(p^i)h(p^{k-i})=h(p^k)+\sum\limits_{i=1}^{k}g(p^i)h(p^{k-i})$，所以可得 $h(p^k)=f(p^k)-\sum\limits_{i=1}^{k}g(p^i)h(p^{k-i})$。时间复杂度为质数个数 $O(\frac{\sqrt n}{\log n})$ 乘枚举质数 $O(\log n)$ 乘以计算 $O(\log n)$，可做到 $O(\sqrt n\log n)$。 --- 计算 $G$： - 直接用公式算。 - 使用杜教筛，特别地如果带记忆化可做到 $O(n^\frac{2}{3})$。 ### Min_25 筛 用到埃筛的一种**思想**。 --- 首先考虑筛 $1\sim n$ 的素数个数。设 $G(n,i)$ 表示第 $i$ 轮埃筛后 $2\sim n$ 剩下的数。显然有 $G(n,0)=n-1$，答案即为 $G(n,\pi(\sqrt n))$。 考虑递推，第 $i$ 轮筛掉的就是 $2\sim n$ 中最小质因子为 $p_i$ 的合数，考虑整体除以 $p_i$，那么答案即为 $G(\lfloor \frac{n}{p_i}\rfloor,i-1)$，但是其中还包含 $1\sim i-1$ 的质数，所以 $G(n,i)=G(n,i-1)-G(\lfloor \frac{n}{p_i}\rfloor,i-1)+i-1$。 时间复杂度可近似为 $O(\frac{n^{\frac{3}{4}}}{\log n})$。用 DP 加滚动，空间复杂度可以做到 $O(\sqrt n)$。同理，用类似的方法可以求得质数和。 一般地，利用上述思想可以求得**完全**积性函数 $f(n)$ 在质数点的函数值之和。 $$ G(n,i)=G(n,i-1)-f(p_i)(G(\lfloor \frac{n}{p_i}\rfloor,i-1)-\sum_{j=1}^{i-1}f(p_j)) $$ --- 回归正题，求积性函数 $f$ 的前缀和 $\sum_{i=1}^{n}f(i)$。 两个要点 - $f$ 在质数 $p$ 处取值是完全积性函数的线性组合。 - $f(p^k)$ 易求。 考虑 $S(n,i)$ 表示 $2\sim n$ 中最小质因子**大于** $p_i$ 的函数值之和，规定 $p_0=1$，则答案表示为 $S(n,0)+f(1)$。这里取大于是为了方便后面求质数处的值。考虑暴力计算（即枚举最小质因子的次幂） $$ S(n,i)=\sum_{j>i}\sum_{k\ge 1,p_j^k\le n}f(p_j^k)(S(\lfloor \frac{n}{p_j^k}\rfloor,j)+1) $$ 为了优化，发现对于 $>\sqrt n$ 的质数 $p_j$，只有它本身的值有效，考虑把质数点值提出来，即 $$ S(n,i)=\sum_{j>i,p_j\le n}f(p_j)+\sum_{j>i,p_j^2\le n}\sum_{k\ge 1,p_j^k\le n}f(p_j^k)(S(\lfloor \frac{n}{p_j^k}\rfloor,j)+[k\ne 1]) $$ 于是对于第一部分，拆成两个 $G$ 之差，但是 $f$ 不一定是完全积性函数，所以如果 $f$ 在 $p$ 处取值能拆成完全积性函数的线性组合或者是低阶多项式，便能求解。 对于第二部分，要求 $f(p^k)$ 易求。直接递归计算且不加记忆化理论是 $O(n^{1-\varepsilon})$，但是实际跑起来很快。 --- 设 $f(x)$ 表示 $x$ 的次大质因子，$f(p)=1$，$f(1)=0$，求 $$ \sum_{i=1}^{n}\sum_{j=1}^nf(\gcd(i,j))^k $$ 化简后为 $$ \sum_{i=1}^{n}f(i)^k\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)\lfloor\frac{n}{ij}\rfloor $$ 后面可以整出分块套整出分块，考虑求解 $f(i)^k$ 的前缀和。 设 $S(n,i)$ 表示 $2\sim n$ 中最小质因子 $>p_i$ 的数的次大质因子之和，$G(n)$ 为 $2\sim n$ 质数个数。由于把 $f(p)$ 考虑上去不太好算，所以最后 $S$ 加上质数个数即可。那么有 $$ S(n,i)=\sum_{j>i,p_j^2\le n}\sum_{e\ge 1,p_j^e\le n}S(\lfloor\frac{n}{p_j^e}\rfloor,j)+p_j^k([\lfloor\frac{n}{p_j^e}\rfloor\ge p_j](G(\lfloor\frac{n}{p_j^e}\rfloor)-j)+[e\ne 1]) $$ $[e>1]$ 是它本身，$G(\lfloor\frac{n}{p_j^e}\rfloor)-j$ 是 $p_j^e$ 乘上一个大于 $p_j$ 的质数。 因为要多次用到，所以可以写递推版的，但是注意要从大到小枚举质数，区分求 $G$。 # 类欧 > 雷欧奥特曼，是圆谷特摄剧《雷欧奥特曼》中的主人公。来自于狮子座·L77星球的炎之战士，精通宇宙拳法的高手，在天龙座D60学习宇宙幻兽拳。因故乡被毁灭而在宇宙中流浪...[详情](https://www.bilibili.com/video/BV1GJ411x7h7) > 前置 > > $$ > ax\le y\Longleftrightarrow x\le\lfloor\frac{y}{a}\rfloor\\ > ax<y\Longleftrightarrow ax\le y-1\Longleftrightarrow x\le\lfloor\frac{y-1}{a}\rfloor\\ > ax>y\Longleftrightarrow x>\lfloor\frac{y}{a}\rfloor\\ > ax\ge y\Longleftrightarrow ax>y-1\Longleftrightarrow x>\lfloor\frac{y-1}{a}\rfloor\\ > x=\sum_{i=1}^{\infin}[i\le x];x^2=\sum_{i=0}^{x-1}(i+1)^2-i^2=\sum_{i=0}^{x-1}2i+1 > $$ “类”是因为思想类似欧几里得。 - $\gcd(a,b)=\gcd(a\%b,b)$，体现为取模。 - $\gcd(a\%b,b)=\gcd(b,a\%b)$，体现为交换顺序。 类欧可通过以上两步递归子问题。 --- 求 $$ f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor\\ g(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor i\\ h(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2 $$ 以 $f$ 为例，给出思想。 >- 取模。 > >如果 $a\ge c$ 或 $b\ge c$，则 $a=c\lfloor\frac{a}{c}\rfloor+a\%c$，$b=c\lfloor\frac{b}{c}\rfloor+b\%c$。带入原式可得 >$$ >\begin{aligned} >f(a,b,c,n)&=\sum_{i=0}^{n}\lfloor\frac{(c\lfloor\frac{a}{c}\rfloor+a\%c)i+(c\lfloor\frac{b}{c}\rfloor+b\%c)}{c}\rfloor\\ >&=\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a\%c,b\%c,c,n) >\end{aligned} >$$ >于是便使得规模减小至 $a<c$ 且 $b<c$。 >- 交换。 > >设 $m=\lfloor\frac{an+b}{c}\rfloor$。 > >$$ >\begin{aligned} >f(a,b,c,n)&=\sum_{i=0}^{n}\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}1\\ >&=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{ai+b}{c}\rfloor>j] >\end{aligned} >$$ >$$ >\lfloor\frac{ai+b}{c}\rfloor>j\Longleftrightarrow ai+b\ge(c+1)j\Longleftrightarrow ai\ge(c+1)j-b >$$ >由前置可得 $i>\lfloor\frac{(c+1)j-b-1}{a}\rfloor$。于是 >$$ >\begin{aligned} >f(a,b,c,n)&=\sum_{j=0}^{m-1}n-\lfloor\frac{(c+1)j-b-1}{a}\rfloor\\ >&=nm-\sum_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}{a}\rfloor >\end{aligned} >$$ >后面是 $f(c,c-b-1,a,m-1)$，为规模更小的子问题。 递归出口为 $a=0$，这样便能在 $O(\log n)$ 的时间复杂度内求解 $f$。$g$ 和 $h$ 同理。 >- 取模。 > >$$ >\begin{aligned} >g(a,b,c,n)&=\sum_{i=0}^{n}\lfloor\frac{(c\lfloor\frac{a}{c}\rfloor+a\%c)i+(c\lfloor\frac{b}{c}\rfloor+b\%c)}{c}\rfloor i\\ >&=\frac{n(n+1)(2n+1)}{6}\lfloor\frac{a}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor+g(a\%c,b\%c,c,n) >\end{aligned} >$$ >- 交换。 > >设 $t_j=\lfloor\frac{cj+c-b-1}{a}\rfloor$。 > >$$ >\begin{aligned} >g(a,b,c,n)&=\sum_{i=0}^{n}\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}i\\ >&=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{ai+b}{c}\rfloor>j]i\\ >&=\sum_{j=0}^{m-1}\sum_{i=t_j+1}^ni\\ >&=\sum_{j=0}^{m-1}\frac{1}{2}(n+t_j+1)(n-t_j)\\ >&=\frac{1}{2}[n(n+1)m-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)] >\end{aligned} >$$ >- 取模。 > >$$ >\begin{aligned} >h(a,b,c,n)&=\sum_{i=0}^{n}\lfloor\frac{(c\lfloor\frac{a}{c}\rfloor+a\%c)i+(c\lfloor\frac{b}{c}\rfloor+b\%c)}{c}\rfloor^2\\ >&=\sum_{i=0}^n(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)^2+\lfloor\frac{a\%ci+b\%c}{c}\rfloor^2+2(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)\lfloor\frac{a\%ci+b\%c}{c}\rfloor\\ >&=\frac{n(n+1)(2n+1)}{6}\lfloor\frac{a}{c}\rfloor^2+(n+1)\lfloor\frac{b}{c}\rfloor^2+h(a\%c,b\%c,c,n)+2\lfloor\frac{a}{c}\rfloor g(a\%c,b\%c,c,n)+2\lfloor\frac{b}{c}\rfloor f(a\%c,b\%c,c,n) >\end{aligned} >$$ >- 交换。 > >$$ >\begin{aligned} >h(a,b,c,n)&=\sum_{i=0}^{n}\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}2j+1\\ >&=\sum_{j=0}^{m-1}2j+1\sum_{i=0}^n[\lfloor\frac{ai+b}{c}\rfloor>j]\\ >&=\sum_{j=0}^{m-1}(2j+1)(n-t_j)\\ >&=\sum_{j=0}^{m-1}2nj+n-2t_jj-t_j\\ >&=nm^2-2g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1) >\end{aligned} >$$ 三个一起递归计算即可。 --- 给定 $a,b,c$，求 $ax+by\le c$ 的非负整数解个数。 推一下式子发现是 $$ \sum_{x=0}^{\lfloor\frac{c}{a}\rfloor}\lfloor\frac{c-ax}{b}\rfloor+1 $$ 但是类欧不能处理负数，于是 $$ \sum_{x=0}^{\lfloor\frac{c}{a}\rfloor}\lfloor\frac{c-ax}{b}\rfloor+1=\sum_{x=0}^{\lfloor\frac{c}{a}\rfloor}\lfloor\frac{c+(b-a)x}{b}\rfloor-x+1 $$ 如果 $b<a$ 那么交换一下即可。 --- 求 $$ \sum_{i=0}^{n}\text{popcount}(ai+b) $$ 把每位拆开统计，即 $$ \sum_{i=0}^{n}\sum_{j=0}^{\log_2(a_i+b)}[\lfloor\frac{ai+b}{2^j}\rfloor\equiv 1\pmod 2] $$ 再拆一下变成 $$ \sum_{i=0}^{n}\sum_{j=0}^{\log_2(a_i+b)}\lfloor\frac{ai+b+2^j}{2^{j+1}}\rfloor-\lfloor\frac{ai+b}{2^{j+1}}\rfloor $$ 显然只有当第 $j$ 位为 $1$ 时值为 $1$，于是枚举 $j$ 变成类欧板子。 --- 求满足 $\frac{a}{b}<\frac{p}{q}<\frac{c}{d}$，要求在 $q$ 最小的前提下 $p$ 最小，保证有解。 考虑在 $q$ 已知下 $p$ 的取值范围。即 $\frac{aq}{b}<p<\frac{cq}{d}$，然后替换成整数范围即 $\lfloor\frac{aq}{b}\rfloor+1\le p\le \lfloor\frac{cq-1}{d}\rfloor$。那么 $p$ 存在当且仅当 $\lfloor\frac{cq-1}{d}\rfloor-\lfloor\frac{aq}{b}\rfloor\ge 1$。 再仔细观察，发现 $\lfloor\frac{cq-1}{d}\rfloor-\lfloor\frac{aq}{b}\rfloor$ 在 $q\ge 1$ 的情况下是 $\ge 0$ 的，所以前缀和具有单调性，便可以二分，然后类欧求解即可。