【置顶】数论进阶

Fan_sheng · 2022-05-26 11:06:57 · 个人记录

基础篇在我自个儿邮箱里

1 拉格朗日插值

求出该多项式在 $k$ 的取值 $f(k)$。

高消可做，\mathbb O(n^3)。

拉格朗日插值法，\mathbb O(n^2)：

显然，当 k=x_i，第 j 项的连乘式分子中一定有 k-x_i 导致该项被消去，第 i 项的连乘式结果一定为 1，所以上式正确。

（据说如果要在 \bmod\ p 意义下进行，要求 p 为质数）

1.1 x 取值连续时

变成如下式子：

如果 x_i\neq i 的话偏移一下就好了

想要快速计算 \prod_{j\neq i}\frac{k-j}{i-j}，分子可以预处理前缀积和后缀积，分母可以化成两个阶乘（但是要注意符号）。复杂度降为 \mathbb O(n)。

1.2 重心拉格朗日插值法

如果需要动态加点，可以在 \mathbb O(n) 时间内完成对答案的修改。

（\LaTeX）

1.3 应用

计算 \sum_{i=1}^ni^k。（定理：该式一定是关于 n 的 k+1 次多项式）

暴力算出前 k+2 项，拉插出式子，代入 n 求解即可。

2 扩展卢卡斯定理/exLucas

求 C_n^m\bmod P，P不一定为质数。

考虑把 P 化成 \prod p_i^{k_i}的形式，求出所有 C_n^m\bmod p_i^{k_i}，再用 CRT 合并即可。

即求

由于两者不互质，逆元不一定有解，所以

前半部分相当于求解下式

我们有

后面两个看上去很乱的部分表示模 p^k 意义下的循环节和余项。

需要消掉 p^{\lfloor\frac{n}{p}\rfloor} 以及 (\lfloor\frac{n}{p}\rfloor)! 中的 p 因子。

有递推式

复杂度 \mathbb O(\log_p^n)。

接下来处理 p^{x-y-z}

根据上面推出来的阶乘的式子，设 g(n) 为 \frac{n!}{p^x} 中的 x，有递推式

那么就可以求出逆元并合并方程了。

模板 Code exLucas

tips：对于 square-free-number，即质因子指数都为 1 的模数，直接使用普通 Lucas 再 CRT 合并即可，比如古代猪文。

3 exBSGS

求 a^x\equiv b\pmod p 最小非负整数解，a,p 不一定互质。

设 d=\gcd(a,p)，根据同余方程的性质我们可以约掉 d。

如果 d\nmid b，只有两种情况：

• 无解。

证明简单，裴蜀定理。

如果整除，我们有

容易发现上面这个式子可以接着约掉 d，直到下面的形式

此时不能再约了，也就是互质。

这里需要注意存在 x\le k 的情况，需要提前判出去。

然后就可以愉快地求得 \frac{a^k}{d^k} 的逆元，用普通 BSGS 求出 x-k。

Code

inline int exBSGS(){
    a%=p,b%=p;
    if(b==1||p==1)return 0;//特判b=1和p=1的情况，答案一定为0 
    int k=0,val=1;//val维护的是(a^k)/(d^k) 
    while(1){
        int d=gcd(a,p);
        if(d==1)break;//已经互质，不再往下化式子 
        if(b%d)return -1;//判无解 
        b/=d,p/=d;k++;
        val=1ll*val*a/d%p;
        if(b==val)return k;//这里代表a^(x-k)（k是当前的k)已经为1，说明x<=k（最终的k），特判出去 
    }
    int x,y;
    exgcd(val,p,x,y);//逆元 
    x=(x%p+p)%p;b=1ll*b*x%p;return BSGS(k);//记得BSGS的结果是x-k，还要加上k 
}

4 Miller Rabin&Pollard Rho

玄学算法不予评价

（\LaTeX）

5 原根

阶：p>1\land\gcd(a,p)=1，使得 a^r\equiv1\pmod p 的最小正整数 r 称为 a 模 p 的阶。

原根：使得 a 模 p 的阶恰为 \varphi(p) 的整数 a 称为 p 的原根之一。

求法：

1. 判断原根个数。n 有原根的充要条件是 n 为 2,4,p^k,2p^k（p 为大于 2 的质数）之一。如果 n 有原根，个数为 \varphi(\varphi(n))。

2. 找最小原根。从 1 到 n-1 暴力枚举 a，可以估计其级别是 n^{\frac{1}{4}} 的。首先需要满足 a^{\varphi(n)}\equiv1\pmod n，然后有性质 a 模 n 的阶一定整除 \varphi(n)，若 \varphi(n)=p_1^{k_1}p_2^{k_2}\cdots，需要对于所有 p_i 满足 a^{\frac{\varphi(n)}{p_i}}\neq1\pmod n。

3. 找所有原根。若最小原根 a_0，那么所有原根可表示为 a_0^k\bmod n，其中 \gcd(k,\varphi(n))=1。暴力即可。

Code 求原根

• 常用原根：998244353 的最小正原根为 3。

• 性质：设 n 有原根 g，对任意 x<n\land \gcd(x,n)=1，x 可以表示为 g^k\bmod p。

• 用途：最重要的当然是用于 NTT。一般应用第三条中的性质，用最小原根的幂次表示一些数，从而把乘方化成幂次的加减。

6 二次剩余

求解同余方程 x^2\equiv n\pmod p，p 为奇质数，x 在模 p 意义下。

二次剩余，即模意义下的开根。以下讨论都以 p 为奇质数，x 在模 p 意义下为前提。

由于笔者实在太蒻，目前只摆结论，证明鸽掉。

（\LaTeX）

称使得该方程有解的 n 为模 p 意义下的二次剩余。

勒让德符号

欧拉判别准则

解的数量

欧拉函数 \varphi(n)

幂函数（一般指数为1） id_k(n)=n^k

莫比乌斯函数 \mu(n)=\left\{\begin{aligned}&1,&n=1\\&0,&n\text有\text指\text数>1\text的\text质\text因\text子\\&(-1)^k,&n\text有k\text个\text质\text因\text子\end{aligned}\right.

约数和函数 \sigma(n)=\sum_{d|n}d

约数个数函数 d(n)=\sum_{d|n}1

以上函数皆为积性函数。

7.1.1 积性函数

积性函数：\forall a,b\in N^+\land\gcd(a,b)=1,f(ab)=f(a)f(b)。

完全积性函数：\forall a,b\in N^+,f(ab)=f(a)f(b)。

利用线性筛几乎可以求解所有积性函数。

7.1.1.1 线性筛 \varphi

phi[1]=1;//注意，因为phi是积性函数
for(int i=2;i<=n;i++){
    if(!check[i]){
        prime.push_back(i);
        phi[i]=i-1;
    }
    for(int j=0;j<prime.size()&&i*prime[j]<=n;j++){
        check[i*prime[j]]=1;
        if(i%prime[j]==0){
            phi[i*prime[j]]=phi[i]*prime[j];
            break;
        }
        phi[i*prime[j]]=phi[i]*(prime[j]-1);
    }
}

7.1.1.2 线性筛 \mu

mu[1]=1;
for(int i=2;i<=n;i++){
    if(!check[i]){
        prime.push_back(i);
        mu[i]=-1;
    }
    for(int j=0;j<prime.size()&&i*prime[j]<=n;j++){
        check[i*prime[j]]=1;
        if(i%prime[j]==0){
            mu[i*prime[j]]=0;
            break;
        }
        mu[i*prime[j]]=-mu[i];
    }
}

7.1.1.3 线性筛 d

（\LaTeX）

7.1.1.4 线性筛 \sigma

（\LaTeX）

7.2 狄利克雷卷积

定义数论函数 f,g 的狄利克雷卷积第 n 项为

性质

• 满足交换律，结合律，函数加法的分配律

• *若 f,g 都为积性函数，$f{g}$ 为积性函数**

• 单位元为 \epsilon。

• 如果对 f 有 f*{g}=\epsilon，称 g 为 f 的逆元。积性函数的逆元是积性函数。

结论

• \mu*{id}=\varphi
• 1*{1}=d
• id*{1}=\sigma

• 莫比乌斯反演：f*{1}=g\Leftrightarrow f=g*{\mu}（重要）

7.2.1 莫比乌斯反演

实际上在上面都说到了，这里只是再专门整理一下与 \mu 相关的。