本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-02 23:30:48

数学啥都不会，最近根据三轮省集 Day6 课件写了几个板子，证明也没咋看。因此本文不包含任何证明，只是记录一下做法方便日后复习。

暂时先写这么多，之后可能会补充，之前的几篇记录也一样。

线性预处理逆元

求 $[1,n]$ 中所有数对 $p$ 取模的逆元，可以递推求解。具体地，设 $p=ik+r,0\le r <i$，即 $p$ 和 $i$ 的带余除法运算。因此有 $ik=-r,\frac 1i=-\frac kr$，即 $inv_i=(p-\lfloor\frac pi\rfloor)inv_{p\bmod i} \bmod p$，代码。

求 $n$ 个数 $a_i$ 对 $p$ 取模的逆元，可以类似阶乘预处理出 $s_i=\prod_{j=1}^i a_j$，并求出 $s_n$ 的逆元，再倒着推出所有 $s_i$ 的逆元 $s'i$。这样 $a_i$ 的逆元即为 $s'_i s{i-1}\bmod p$，代码。事实上上个问题也能这么做。

扩展欧几里得算法（Exgcd）：P5656

给定 $a,b,c$，求解 $ax+by=c$ 的整数解 $(x,y)$。根据裴蜀定理，当且仅当 $\gcd(a,b)\mid c$ 时有解。因此先求解 $ax+by=\gcd(a,b)$，根据辗转相除法有 $\gcd(a,b)=\gcd(b,a\bmod b),b\ne 0$，因此列出另一个式子 $bx'+(a\bmod b)y'=ax+by$。将 $a\bmod b$ 写成 $a-\lfloor\frac ab\rfloor b$，合并 $a,b$ 同类项得到 $ay'+b(x'-\lfloor\frac ab\rfloor y')=ax+by$，据此可以递归求出 $x',y'$ 再反推出 $x,y$，在 $b=0$ 时返回 $x=1,y=0$，即可得到一组可行解 $x,y$。

设 $\gcd(a,b)=g$，此时有 $X=\frac {cx}g,Y=\frac{cy}g$ 为满足题意的一组解。有时会在一些限制下求 $X,Y$ 的最值，只需要知道所有解均满足 $X'=X+\frac{kb}g,Y'=Y-\frac{ka}g$ 即可，容易求最小正整数解之类的最值，时间复杂度 $O(\log V)$，代码。

中国剩余定理（CRT）：P1495

给出 $n$ 个同余方程 $x\equiv b_i\pmod {a_i}$，$a_i$ 两两互质，求满足所有方程的最小非负整数 $x$。考虑在不影响其他限制的前提下满足第 $i$ 个限制。具体地，设 $M=\prod_{i=1}^n a_i,c_i=\frac M{a_i}$，即 $c_i$ 为除 $i$ 外的所有模数之积。之后求出 $c_i$ 在模 $a_i$ 意义下的逆元 $c_i^{-1}$，最后求出 $r=\sum_{i=1}^n c_ic_i^{-1}b_i$ 即为可行解，对 $M$ 取模可得最小解。

这里可以感性理解，每一项由于有 $c_i$ 作为系数，不会对其他方程造成影响；而在模 $a_i$ 意义下为 $b_i$，满足了该方程的限制。由于用到了逆元，要求模数两两互质，求逆元使用 Exgcd 即可，时间复杂度 $O(n\log V)$，代码。据说拉格朗日差值也是类似思想。

扩展中国剩余定理（ExCRT）：P4777

题意同上，然而不再保证模数互质。考虑直接暴力合并两个方程，可将原式化为 $x-k_ia_i=b_i,x=k_ia_i+b_i$。因此若有 $A,B$ 和 $a,b$ 两个方程，则有 $AK+B=ak+b$，即 $ak-AK=B-b$，其中只有 $k,K$ 未知，可以直接代入 $a,A,B-b$ 用 Exgcd 求出 $k,K$ 的解。之后求出 $b'=b+ka,a'=\frac{aA}g$，$b'$ 对 $a'$ 取模后得到的 $a',b'$ 方程即与上面两个方程等价。

每次合并两个方程，直到只剩一个为止，最终的 $b$ 即为最小非负解。时间复杂度 $O(n\log V)$，代码。所以其实 ExCRT 和 CRT 完全没啥关系，泛用性高的同时可能还容易一些。

卢卡斯定理（Lucas）：P3807

给出 $n,m,p$，求 ${n+m\choose n}\bmod p$，$p$ 为质数。卢卡斯定理即 ${n\choose m}\bmod p={n\bmod p\choose m\bmod p}\times {{\lfloor\frac np\rfloor}\choose {\lfloor \frac mp \rfloor}}$，还有一种用 $p$ 进制的写法，两种是等价的。因此求组合数时可以不断递归，直到 $n,m$ 均小于 $p$ 时再暴力求解。这里若预处理 $p$ 以内的阶乘及其逆元，可以 $O(1)$ 计算。时间复杂度 $O(p+\log_pV)$，代码。

扩展卢卡斯定理（ExLucas）：P4720

题意同上，然而不再保证模数 $P$ 为质数。考虑把组合数拆成阶乘形式 $\frac{n!}{m!(n-m)!}$，然而模数不为质数时不一定有逆元。因此将模数 $P$ 质因数分解为若干 $p^k$，求出这些 ${n\choose m}\bmod p^k$ 的值，再用 ExCRT 合并出答案。

考虑如何求该值，先把所有 $p$ 全拿出来，即变为 $\frac{\frac {n!}{p^x}}{\frac{m!}{p^y}\times \frac{(n-m)!}{p^z}}\times p^{x-y-z}$。现在需要快速求 $n!$ 中除掉所有 $p$ 因子后对 $p^k$ 取模的结果，以及除去的 $p$ 因子个数，分别设这两个值为 $f(n),g(n)$。显然有 $g(n)=g(\lfloor\frac np\rfloor)+\lfloor\frac np\rfloor$，以及 $f(n)=f(\lfloor\frac np\rfloor)+\lfloor\frac np\rfloor s_{p^k}+s_{n\bmod p}$，其中 $s_i$ 表示 $[1,i]$ 中不为 $p$ 倍数的所有数乘积，可以 $O(p^k)$ 预处理出来。含义即先将 $p$ 的倍数取出并除以 $p$，在 $f(n)$ 计算时还用到了模 $p^k$ 的循环节性质。

这样答案即为 $\frac{f(n)}{f(m)f(n-m)}\times p^{g(n)-g(m)-g(n-m)}\bmod p^k$，由于 $f$ 值中不含 $p$ 因子，一定与 $p^k$ 互质，可以直接用 Exgcd 计算逆元。总时间复杂度可以分析到 $O(P\log P)$，代码。所以其实 ExLucas 和 Lucas 基本没啥关系，泛用性高的同时可能还容易一些。

大步小步算法（BSGS）：P3846

给定质数 $p$ 和 $b,n$，求最小非负整数 $l$ 使得 $b^l\equiv n\pmod p$。显然答案不会超过 $p$，因为 $p$ 次后一定会出现循环节。考虑设 $B=\sqrt p,l=kB-t,t<B$，有 $b^{kB-t}\equiv n\pmod p$。由于 $p$ 为质数，一定存在逆元，可以直接除过去得到 $b^{kB}\equiv nb^t\pmod p$。这时两边都只有 $O(\sqrt p)$ 种取值，枚举出来找到相等的最小 $kB-t=l$ 即可。时间复杂度为 $O(\sqrt p)$ 或 $O(\sqrt p\log p)$，代码。

扩展大步小步算法（ExBSGS）：P4195

题意同上，然而不再保证 $p$ 为质数。由于 $b,p$ 不一定互质，可能出现没有逆元的情况。考虑去掉 $b,p$ 的公因子，具体地，先改写成 $b^l-tp=n$，即 $b\times b^{l-1}-pt=n$，这时求出 $d=\gcd(b,p)$，若 $d\nmid n$ 则无解，否则可将 $b,p,n$ 同除 $d$。之后若 $gcd(b,p)$ 仍不为 $1$ 则重复此操作，直到 $b,p$ 互质。

这时得到的式子转化回去为 $Kb^{l-k}\equiv n\pmod p$，其中 $b,p$ 互质，$K$ 为 $k$ 个 $b$ 消掉公因子后剩余部分之积对最终 $p$ 取模的结果。此时就可以直接使用普通 BSGS 解决了，求出答案加上 $k$ 即为最终答案。注意要特判答案不超过 $k$ 的情况，只需在 $K=n$ 时确定目前 $k$ 为答案即可。时间复杂度为 $O(\log p+\sqrt p)$，代码。所以 BSGS 的扩展是转化为能解决的有逆元情况，再套用普通 BSGS 求解的，比之前的两组算法关系密切得多。

求欧拉函数

若要预处理 $[1,n]$ 内的欧拉函数，可以使用线性筛法，令质数 $p$ 的 $\arphi(p)=p-1$，在筛时若 $p_j\mid i$，则令 $\arphi(ip_j)=\arphi(i)\times p_j$，否则令 $\arphi(ip_j)=\arphi(i)\times \arphi(p_j)=\arphi(i)\times(p_j-1)$，这里基于每个质因子 $p$ 都会给欧拉函数值乘上 $\frac{p-1}p$。代码：

phi[1]=1;
for(int i=2;i<=P;i++)
{
	if(!f[i]) p[++ct]=i,phi[i]=i-1;
	for(int j=1;j<=ct&&1ll*i*p[j]<=P;j++)
	{
		f[i*p[j]]=1;
		if(i%p[j]==0)
		{
			phi[i*p[j]]=phi[i]*p[j];
			break;
		}
		phi[i*p[j]]=phi[i]*(p[j]-1);
	}
}

若要求单个数的欧拉函数值，则可以直接枚举其所有质因子，并按照上面所说的 $\frac{p-1}p$ 计算出答案。代码见下一题的提交记录。

扩展欧拉定理：P5091

求 $a^b\bmod m$，其中 $m\le 10^{8},a\le 10^9,b\le 10^{2\times 10^7}$。扩展欧拉定理即为：

$$a^b\equiv\left\{\begin{matrix}a^b&,b<\arphi(m)\^{b\bmod\arphi(m)+\arphi(m)}&,b\ge\arphi(m)\end{matrix}\right.\pmod m$$，

当然 $\gcd(a,m)=1$ 时有欧拉定理 $a^{\arphi(m)}=1,a^b\equiv a^{b\bmod \arphi(m)}\pmod m$。

因此类似快读读入 $b$ 的每一位，过程中一直对 $\arphi(m)$ 取模即可。时间复杂度为 $O(\sqrt m+\lg(b)+\log m)$，分别为求欧拉函数，读入和快速幂的复杂度，代码。

拉格朗日插值：P4781

给出 $n$ 个点 $(x_i,y_i)$，保证 $x_i$ 互不相同，求一个 $(n-1)$ 次多项式使得 $\forall i,f(x_i)=y_i$，$n\le 2000$。考虑对每个点构造一个多项式 $g_i(x)$，使得 $g(x_i)=y_i,\forall j\ne i,g(x_j)=0$，则 $\sum g_i$ 即为合法的 $f$。一种合法构造为 $g_i(x)=y_i\cdot\prod_{j\ne i} \frac{x-x_j}{x_i-x_j}$，本题直接带入计算即可。若需要求出多项式 $f(x)$ 的系数，可以先计算出 $a_i=\frac{y_i}{\prod_{j\ne i}x_i-x_j}$，再预处理出多项式 $t(x)=\prod x-x_i$ 的系数，每次先求出 $g(x)=\frac{t(x)}{x-x_i}$，再将 $a_i\cdot g(x)$ 加给 $f(x)$ 即可。时间复杂度 $O(n^2)$，提交记录。更低复杂度需要多项式科技，不学。

莫比乌斯反演

定义 $i$ 存在平方因子时 $\mu(i)=0$，否则若其质因子个数为 $k$，$\mu(i)=(-1)^k$。

莫比乌斯函数 $\mu$ 可线性筛求出，有 $\mu(1)=1,\mu(p)=-1$。否则有 $x=i\cdot y$，其中 $y$ 为 $x$ 最小质因子，则若 $y\mid i$，$\mu(x)=0$，否则 $\mu(x)=-\mu(i)$。

定义狄利克雷卷积运算 $\st$ 为 $h=f\st g$ 时 $h(x)=\sum_{d\mid x} f(d)g(\frac xd)$。

定义数论函数 $id(x)=x,1(x)=1,\arepsilon(x)=[x=1]$。

有性质 $\sum_{d\mid n}\mu(d)=[n=1]=\arepsilon(n)$，即 $\mu\st1=\arepsilon$。

还有性质 $\sum_{d\mid n}\arphi(d)=n$，即 $\arphi \st1=id$。

上式两边卷上 $\mu$ 得到 $\arphi\st\arepsilon=id\st\mu$，展开得到 $\arphi(n)=\sum_{d\mid n}d\cdot\mu(\frac nd)$。

P4450 双亲数

$T\le 5\times 10^4$ 次询问，每次给定 $A,B,d\le 5\times 10^4$，求 $\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d]$。先将 $i,j$ 均除掉 $d$，得到 $\sum_{i=1}^{\lfloor\frac Ad\rfloor}\sum_{j=1}^{\lfloor\frac Bd\rfloor}[\gcd(i,j)=1]$，将其用性质展开得到 $\sum_{i=1}^{\lfloor\frac Ad\rfloor}\sum_{j=1}^{\lfloor\frac Bd\rfloor}\sum_{k\mid\gcd(i,j)}\mu(k)$。交换求和号，将 $k$ 放在最前面，得到 $\sum_{k=1}^{\lfloor\frac{\min(A,B)}d\rfloor}\sum_{i=1,k\mid i}^{\lfloor\frac Ad\rfloor}\sum_{j=1,k\mid j}^{\lfloor\frac Bd\rfloor} \mu(k)$。该式的值显然为 $\sum_{k=1}^{\lfloor\frac{\min(A,B)}d\rfloor}\mu(k)\lfloor\frac A {dk}\rfloor\lfloor\frac B {dk}\rfloor$。

线性筛出所有 $\mu $ 的值，本题已经可以做到单次查询线性。然而多次询问时无法通过。考虑对后面的部分整除分块，则两个除式各有 $O(\sqrt V)$ 种取值，两式均不变的连续段数量也是 $O(\sqrt V)$ 级别的。因此对 $\mu$ 预处理前缀和即可做到 $O(V+T\sqrt V)$ 的复杂度，提交记录。

P2257 YY的GCD

$T\le 10^4$ 次询问，每次给定 $n,m\le10^7$，求 $i\in[1,n],j\in[1,m]$ 中有多少对 $(i,j)$ 满足 $\gcd(i,j)$ 为质数，设质数集合为 $P$。直接列出式子 $\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)\in P]$，并改为先枚举质数为 $g$，得到 $\sum_{g=2,g\in P}^{\min(n,m)}\sum_{x=1}^n\sum_{y=1}^m[\gcd(x,y)=g]$，然后用上题的过程拆开得到 $\sum_{g=2,g\in P}^{\min(n,m)}\sum_{k=1}^{\lfloor\frac{\min(A,B)}g\rfloor}\mu(k)\lfloor\frac A {gk}\rfloor\lfloor\frac B {gk}\rfloor$。

令 $T=gk$，则原式变为 $\sum_{T=2}^{\min(n,m)}\lfloor\frac AT\rfloor\lfloor\frac BT\rfloor \sum_{g\mid T,g\in P}\mu(\frac Tg)$，需要求出 $f(T)=\sum_{g\mid T,g\in P}\mu(\frac Tg)$。考虑在线性筛过程中预处理，有 $f(1)=0,f(p)=1$。否则有 $x=iy$，其中 $y$ 为 $x$ 的最小质因子。若 $y\mid i$ 则 $g\ne y$ 时 $\frac xg$ 包含 $y^2$ 因子，一定没有贡献，因此只有 $g=y$ 有贡献 $f(x)=\mu(i)$；否则 $f(x)=\sum_{g\mid T,g\in P}\mu(\frac Tg)+\mu(i)=\sum_{g\mid i}\mu(\frac {iy}g)+\mu(i)=-f(i)+\mu(i)$。之后对 $f$ 求前缀和并整除分块求解即可，时间复杂度 $O(V+T\sqrt V)$，提交记录。

P2398 GCD SUM

给定 $n\le 10^7$，求 $\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)$。直接拆并转化成 $\sum_{g=1}^n g\cdot\sum_{k=1}^{\lfloor\frac ng\rfloor}\mu(k)(\lfloor\frac n {gk}\rfloor)^2$，同样令 $T=gk$ 得到 $\sum_{T=1}^n(\lfloor\frac n {T}\rfloor)^2 \sum_{g\mid T}g\cdot\mu(\frac Tg)$，然后试图爆推线性筛式子失败了。事实上上面有性质表明 $\sum_{g\mid T}g\cdot\mu(\frac Tg)=\arphi(T)$，因此线性筛欧拉函数即可做到 $O(n)$ 和多组 $O(n+T\sqrt n)$ 的复杂度，提交记录。

狄利克雷前缀和：P5495

用于解决求 $b_i=\sum_{j\mid i}a_j$ 或 $c_i=\sum_{i\mid j}a_j$ 的问题及其逆问题，时间复杂度 $O(n\ln \ln n)$。该问题的暴力做法为枚举每个数的倍数，时间复杂度 $O(n\ln n)$。

考虑以每种质因子为一维，此时每个下标是高维内一个点，$i$ 的因数是每一维均不大于其的点，倍数是每一维均不小于其的点。因此在该意义下对 $a$ 数组做高维前缀和即可得到 $b$，做高维后缀和即可得到 $c$。具体实现仍然在一维数组内，枚举每个质因数 $p$，并按某种顺序枚举所有 $ip\le n$ 更新即可。注意前缀和正序，后缀和逆序枚举，逆问题差分时与原问题顺序相反。时间复杂度分析方式同埃氏筛，我都不会，是 $O(n\ln\ln n)$ 的，提交记录。

U540870 课后习题 2

给定长为 $n$ 的序列 $a$，求序列 $b$ 使得 $b_i=a_i+\sum_{j\mid i,j<i} b_j$。$n\le 2\times 10^7$。注意到 $j\mid i,j<i$ 的 $j$ 一定不超过 $\lfloor\frac i2\rfloor$，因此通过值域倍增的方式来保证计算 $b_i$ 时所需 $b_j$ 的值均已确定。

具体地，设 $m$ 表示目前 $[1,m]$ 内的 $b_i$ 均处理好了。每次取 $m'=\min(2m,n)$，然后处理 $[m+1,m']$ 内的所有 $b$。此时先将 $[1,m]$ 内的 $b$ 复制一份到 $t$ 中，之后在 $t$ 上做 $[1,m']$ 的狄利克雷前缀和，得到的 $t_i,i\in[m+1,m']$ 即为 $\sum_{j\mid i,j<i} b_j$，因此有 $b_i=a_i+t_i$，这样就完成了这部分 $b$ 的求解，最后更新 $m=m'$ 即可。

下面分析时间复杂度，大概是 $\sum_{i=0,2^i\le n} O(2^i\ln\ln(2^i))$，在 $i$ 最大时的取值大概为 $O(n\ln\ln n)$，且 $i$ 较小的情况下复杂度总和不超过该值，这是由于 $\sum_{j=0}^{i-1} 2^j=2^i-1$。因此总时间复杂度仍是 $O(n\ln\ln n)$ 的，提交记录。