数论学习

2020-04-24

在这一天，我开始了系统的学习数论

筛素数

埃氏筛素数，线筛法

整除与同余

exgcd与gcd

乘法逆元

线性递推求逆元，扩展欧几里德求逆元，费马小定理求逆元($P$必须为素数)

唯一分解定理: 每一个正整数可以唯一的表示成素数的乘积，换句话说，对于任意正整数$n$,可以得到
$$
n=2^{a_1}*3^{a_2}*5^{a_3}*\cdots
$$

定理1:

$$
a*b=gcd(a,b)*lcm(a,b)
$$

欧几里德算法:

int gcd(int a,int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}

裴蜀定理: 对于任意两个完全为0的正整数a,b存在$xa+yb=gcd(a,b)$
代码实现:

int exgcd(int b,int a,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int tmp=gcd(b,a%b);
    int t=x;
    x=y,y=t-a/b*y;
    return tmp
}

乘法逆元： 存在$x$使$ax\equiv 1\pmod P $成立，那么就称$x$为$a$关于$P$的乘法逆元，

定理：$a$关于$P$的乘法逆元存在的充要条件是$gcd(a,p)=1$

如果逆元存在，则在$0$到$P-1$范围内有且仅有一个逆元。

作用： 当需要求$\frac{a}{b}mod(P)$时，其中 a 很大，那么我们可以求出 $b$关于$P$的乘法逆元$x$,则有$\frac{a}{b}\equiv(a\cot x)\pmod P$

费马小定理： 假如 P 是素数，且$gcd(a,P)=1$那么就有$a^{p-1}\equiv 1\pmod P$

我们可以推理得到$a\cdot a^{p-2}\equiv 1\pmod P$，那么根据定义,$a^{p-2}$即为$a$的逆元，其中$a^{p-2}$可以通过快速幂来求

龟速乘

将乘法进行二进制拆分，分步取模防止单次乘法溢出,代码类似于快速幂，只需要将其中的乘法换成加法

代码实现

inline ll slow(ll a,ll b,ll mod)
{
    ll ans=0;
    if(b<0)b=(b%mod+mod)%mod;//如果 b 为负数，龟速乘可能会炸掉，所以先取模将b改为正整数
    while(b)
    {
        if(b%2)ans=(ans+a)%mod;
        b=b>>1;
        a=(a<<1)%mod;
    }
    return ans;
}

咕咕分界线1

中间的时间被咕咕吃了,咕咕好心的给了地址

2020-05-01

终于，今天到了学习数论的第三天，开始了快乐的$Catalan$数，也就是组合数的学习

组合数

杨辉三角，组合数问题

卢卡斯定理

卢卡斯定理: 设$P$为质数，$a,b$都为正整数，并且

$ a=a_kp^k+a_{k-1}p^{k-1}+a_{k-2}p^{k-2}+\cdots+a_1p+a_0 $
$ b=b_kp^k+b_{k-1}p^{k-1}+b_{k-2}p^{k-2}+\cdots+b_1p+b_0 $

其中$1<=a_i,b_i<=p-1,i=0,1,2,3,\cdots,k$，那么就有
$$
C_b^a\equiv C_{b_k}^{a_k}\times C_{b_{k-1}}^{a_{k-1}}\times C_{b_{k-2}}^{a_{k-2}}\times\cdots C_{b_0}^{a_0}\pmod p
$$

用递归写出来就是

    Lucas(n,m)%p=Lucas(n/p,m/p)*Catalan(n%p,m%p)%p

证明过程

咕咕分界线2

拓展卢卡斯定理 PS: 感觉和卢卡斯定理关系不大

咕咕分界线3

2020-05-09

今天开始了欧拉定理的学习

欧拉定理： $\phi(n)$表示从$1-n$的正整数中与$n$互质的数的个数

拓展欧拉定理 :
$$
a^c=
\begin{cases}
a^{c\bmod\phi(m)}(gcd(a,m)==1)\\
a^c(gcd(a,m)\neq1,c<\phi(m))\\
a^{(c\bmod\phi(m))+\phi(m)}(gcd(a,m)\neq1,c\geq\phi(m))
\end{cases}
\pmod m
$$

咕咕分界线4

2020-07-28