【学习记录】数学

KSCD_ · 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 的 \varphi(p)=p-1，在筛时若 p_j\mid i，则令 \varphi(ip_j)=\varphi(i)\times p_j，否则令 \varphi(ip_j)=\varphi(i)\times \varphi(p_j)=\varphi(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}。扩展欧拉定理即为：