OI 里的数学内容整理

发布于 2021-04-14  194 次阅读


本博客仅罗列定理,不给出证明,如需要请自行搜索。

质数相关

线性筛素数

inline void sieve(int n){//线性筛求 pri 和 phi
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;}
        for(int j=1;j<=cnt&&pri[j]*i<=n;j++){
            vis[pri[j]*i]=1;
            if(!(i%pri[j])){phi[i*pri[j]]=pri[j]*phi[i];break;}
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
}

phi 为下文的欧拉函数,线性筛过程可以顺便求出,pri 即为素数数组。

算术基本定理

任何一个大于 $1$ 的正整数 $N$ 都能唯一分解为有限个质数的乘积,即:$N=p_1^{c_1}p_2^{c_2}\dots p_m^{c_m}$。

约数相关

欧几里得算法相关

裴蜀定理

对于 $ax+by=\gcd(a,b),\ a,b \in N$,一定存在一组整数 $x,y$ 使得该式成立。

扩展:对于 $a_1x_1+a_2x_2 \dots+a_nx_n=\gcd(a_1,a_2 \dots a_n),\ a_i\in N$,一定存在一组整数 $x_1,x_2\dots x_n$ 使得该式成立。

朴素欧几里得

$\gcd(a,b)=\gcd(b,a\bmod b)$。

扩展欧几里得

求解 $ax+by=\gcd(a,b),\ a,b \in N$ 的一组整数解 $(x,y)$。

inline void exgcd(int a,int b){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b);
    int t=x;x=y;y=t-(a/b)*y;
}

时间复杂度:$O(\log n)$。

应用:扩欧求逆元

求 $a\pmod{b}$ 意义下的逆元等价于求一个 $x$ 满足 $ax\equiv1\pmod{b}$,由于逆元存在,$a$ 与 $b$ 互质,故 $\gcd(a,b)=1$,所以即求 $ax+by=1=\gcd(a,b)$ 的解 $x$,显然可以用扩欧解决。

欧拉函数

记 $\varphi(n)$ 为 $\le n$ 的正整数中与 $n$ 互质的数的个数(因此 $\varphi(1)=1$)。

通式:$\varphi(n)=n \prod\limits_{i=1}^{n}(1-p_i)$,其中 $p_1,p_2\dots p_n$ 为 $n$ 的所有不重复的质因数。

容易发现,当 $p$ 为一个质数时,有 $\varphi(p)=p-1$。

同余相关

欧拉定理相关

欧拉定理

对于任意互素的 $a$ 和 $p$,有 $a^{\varphi(p)}\equiv 1\pmod{p}$。

推论:若 $a$ 和 $p$ 互素,则有 $a^b\equiv a^{b \bmod \varphi(p)} \pmod{p}$。

费马小定理

若 $p$ 为素数且 $a$ 和 $p$ 互素,则有 $a^{p-1}\equiv 1\pmod{p}$。

应用:费马小定理求逆元

仅在模数为质数时适用

若 $p$ 为质数,由 $a^{p-1}\equiv 1\pmod{p}$,故 $a \times a^{p-2}\equiv 1 \pmod{p}$,故 $a^{p-2}$ 即为 $a\pmod{p}$ 意义下的逆元,显然可以快速幂解决。

扩展欧拉定理

同余方程组相关

中国剩余定理

组合相关

卡特兰数

记 $f_n$ 为第 $n$ 项卡特兰数。

递推式

$f_1=1,f_n=f_{n-1}\frac{4n-2}{n+1}$。

通项式

$f_n=\frac{C_{2n}^n}{n+1}=C^n_{2n}-C^{n-1}_{2n}$。

矩阵相关

To be continue……


月流华 岁遗沙 万古吴钩出玉匣