数论知识荟萃

有参考算法竞赛进阶指南。。

一、质数

定义：质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，则称之为质数。

(1) 判定：

对于数(N)，若之为合数，则存在一个数(T)能整除它其中，(2<=T<=sqrt{N})

复杂度：(O(sqrt{n}))

(2) 筛法：

对于数(N)，我们要求出(1) ~ (N)的所有素数。

直接介绍线性筛法，对于数(m)，我们考虑仅用它的最小质因子(q)筛去它，这是线筛的最基本思想。

#include <cstdio>
const int N=1000010;
int v[N],prime[N],cnt=0,n;
//v[i]代表i的最小质因子，prime[i]代表第i的素数是多少
void Prime()
{
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=i;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++)
        {
            int k=prime[j]*i;
            if(v[i]<prime[j]||k>n) continue;
            v[k]=prime[j];
        }
    }
}
int main()
{
    scanf("%d",&n);
    Prime();
    for(int i=1;i<=cnt;i++)
        printf("%d ",prime[i]);
    return 0;
}

复杂度：(O(n))

(3) 质因数分解

算术基本定理：任何一个大于1的整数都能被分解成有限个质数的乘积

即(N=p_1^{c^1}p_2^{c^2}...p_m^{c^m})或(N=prod_{i=1}^m{p_i}^{c_i})

当不考虑顺序时，分解具有唯一性

这点在后面用的很多。

质因数分解：
和判定是否是质数有点像，我们用(1) ~ (sqrt{N})中的每一个数去试除(N)

复杂度：(O(sqrt{N}))

二、约数

(1) 整除，约数

整除的概念：一般的，设a，b为整数，且b≠0.如果存在整数q，使得a=bq，称b整除a，记作(b|a)，也称b是a的约数。如果p不存在，称b不整除a，记作(b mid a).

整除的性质：

a|b,b|a (Rightarrow) a=b或a=-b

a|b,b|c (Rightarrow) a|c

a|b,a|c (Rightarrow) 对任意整数x,y，有a|bx+cy

若(a|bc),且((a,b))=(1),则(a|c)

设整数 (a) , (b) 不同时为0,则存在一对整数 (m) , (n) ,使得((a,b)=am+bn)（在一次同余方程和不定方程中经常用到）【裴蜀定理】

(2) 最大公约数与最小公倍数

定义：(gcd(a,b))(或((a,b)))为最大公因数，(lcm[a,b])(或([a,b]))为最小公倍数
欧几里得算法：((a,b)=(b,a) (mod) (b))

欧几里得就不证明了吧。

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

((a,b)[a,b]=|a||b|)

(3) 算术基本定理的推论：

(N=p_1^{c^1}p_2^{c^2}...p_m^{c^m})

(N)的正约数个数：
(prod_{i=1}^m (c^i+1))
(N)的正约数之和：
((1+p_1+p_1^2+...+p_1^{c_1})*...*(1+p_m+p_m^2+...+p_m^{c_m})=prod_{i=1}^m(sum_{j=0}^{c_i} (p_i)^j))

(4) 互质

对整数(a,b),若(gcd(a,b)=1),则称(a)与(b)互质。

(5) 欧拉函数

定义：(1) ~ (N)中与(N)互质的数的个数，称为欧拉函数，记为(φ(N))

计算式
对(N)进行算术基本定理分解，即(N=p_1^{c^1}p_2^{c^2}...p_m^{c^m})或(N=prod_{i=1}^m{p_i}^{c_i})
则(φ(N)=(1-1/p_1)*(1-1/p_2)*...*(1-p_m))即(φ(N)=prod_{i=1}^m(1-1/p_i))
感性证明（即并不是那么确切的，只是能加深记忆的证明·）：
对于(N)的某个质因子(p)，(p*k)一定于(N)不互质（(kin N^*,k*p<N)），即筛去后为(N-N/p)
若此时引入第二个因子(q)，同理筛去(N/q)，但是多筛去了(q)与(p)的公共倍数，加回来，即为
(N-N/p-N/q+N/(q*p)=N(1-1/p)(1-1/q)),~~以此类推~~

计算式(O(sqrt N))求解(φ(N))

ll get(ll k)
{
    ll eu=k;
    for(ll i=2;i*i<=k;i++)
    {
        if(k%i==0)
            eu=eu*(i-1)/i;
        while(k%i==0)
            k/=i;
    }
    if(k>1) eu=eu*(k-1)/k;
    return eu;
}

性质
①若(gcd(a,b)=1),则(φ(ab)=φ(a)*φ(b))
感性证明：带入欧拉函数定义式即可。
【拓展】
完全积性函数：是指所有对于任何(a,b)都有性质(f(ab)=f(a)f(b))的数论函数。
积性函数：是指所有对于(gcd(a,b)=1)的(a,b)都有性质(f(ab)=f(a)f(b))的数论函数。
②若质数(q)满足(q|n)且(q^2|n),则(φ(q)=φ(n/q)*q)
代入计算式可以得到
③若质数(q)满足(q|n)且(q^2 mid n),则(φ(q)=φ(n/q)*(q-1))
由积性函数性质得到
④(sum_{d|n}φ(d)=n)
先证明是积性函数，再讨论单因子情况即可
⑤(φ(n)*n/2=sum_{d},gcd(d,n)=1)
若(gcd(x,n)=1),则(gcd(n-x,n)=1)。即它们是成对存在的。
对于以上证明，其实自己多证几遍就记住了。
求解(φ(N))
将(N)分解质因数后，代入定义式计算。
复杂度：(O(sqrt{N}))
求解(φ(1))~(φ(N))
借助性质①②③和线性筛的思想。
我们在线性筛筛去合数的同时推出这个合数的(φ(i))
code：

int v[N],prime[N],phi[N],cnt=0,n;
void eular()
{
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=i;
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt;j++)
        {
            int tmp=i*prime[j];
            if(v[i]<prime[j]||tmp>n) break;
            v[tmp]=prime[j];
            phi[tmp]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
}

三、同余

(1)同余的概念：一般的，设n为正整数，a和b为整数，如果a和b被n除后余数相同，那么称a和b模n同余，记作(a≡b) ((mod) (n))

(2)同余的性质：

(a≡b) ((mod) (n)) (Leftrightarrow) (n|a-b)
若(a≡b) ((mod) (n))，且(c≡d) ((mod) (n))，
① (a+c≡b+d) ((mod) (n))
② (ac≡bd) ((mod) (n))
①(ka≡kb) ((mod) (n)) (k为任意整数)
②若(ab≡ac) ((mod) (n)),设(d=(a,n)),则(b≡c) ((mod) (n/d))
(a^m≡b^m) ((mod) (n)) (m为正整数)

这里证明一下第三条第二点
(ab≡ac) ((mod) (n)) (d=(a,n))
(Rightarrow n | a(b-c))
(Rightarrow n/d |a(b-c)/d)
由(gcd(n/d,a/d)=1)
(Rightarrow n/d |(b-c))
(Rightarrow b≡c(mod n/d))

(3)一次同余方程求解（exgcd或者叫大衍求一术）：

对于一次同余方程(ax≡b(mod m))
(Rightarrow m|ax-b)
设(-ym=ax-b)
即为(ax+my=b)
转化为求解一元二次不定方程

对(ax+by=d)
当(gcd(a,b)|d)时，有整数解

证明即求解方法：
由欧几里得：(gcd(a,b)=gcd(b,r)=...=gcd(a_n,0))
使用数学归纳法
对最后一步：(a_n*x_n+0*y_n=a_n)
显然对这个方程有解(x_n=1,y_n=0)
若(a_m*x_m+b_m*y_m=d)有解
则对(a_{m-1}*x_{m-1}+b_{m-1}*y_{m-1}=d)
有(b_{m-1}=a_m,a_{m-1}=lfloor a_{m-1}/a_m floor*a_m+b_m)(gcd得出)
(Rightarrow (lfloor a_{m-1}/a_m floor *a_m+b_m)*x_{m-1}+a_m*y_{m-1}=d)
(Rightarrow (k*x_{m-1}+y_{m-1})*a_m+x_{m-1}*b_m=d)
(Rightarrow x_{m-1}=y_m,y_{m-1}=x_m-lfloor a_{m-1}/a_m floor *y_m)
由以上，我们得到了它的证明和解法

(4)欧拉定理

若(gcd(a,n)=1),则有(a^{φ(n)}≡1(mod) (n))

证明：
定义简化剩余类：把所有与整数a(a与n互质)模n同余的整数构成的集合叫做模n的一个简化剩余类，记作(a[n])，并把a叫做简化剩余类(a[n])的一个简化剩余系。

先证明当集合(x)恰好遍历(即取遍)(n)每一个简化剩余系时，(kx)也遍历。((k)为任意整数，(gcd(x,n)=1))

反证：若有(kx_i≡kx_j (mod) (n))
则 (x_i≡x_j (mod) (n))
矛盾，得证

下面欧拉定理：
设({overline{a_1},overline{a_2},...,overline{a_φ(n)}})是(n)的一个简化剩余类
由上({overline{a*a_1},overline{a*a_2},...,overline{a*a_φ(n)}})也是
则(a*a_1*a*a_2...a*a_{φ(n)}≡a_1*a_2...a_{φ(n)} (mod) (n))
则(a^{φ(n)}≡1(mod) (n))

特别的，当(n)取质数时，有(φ(n)=n-1)
则(a^{n-1}≡1 (mod) (n))，即为费马小定理

(5)乘法逆元

对于"+"、"-"、"*"，我们都已经得到了它在mod p下的转换式，那么对于"/"呢？

定义：若整数(b,m)互质，并且(b|a)，则存在一个整数(x)，使得(a/b≡a*x(mod) (m))。称(x)为(b)的乘法逆元，记为(b^{-1}≡(mod) (m))
对于这个有解性可以转换成一次同余方程的有解来证明，不多赘述。

求法：(a/b≡a*b^{-1}≡a/b*b*b^{-1}(mod) (m)),即(b*b^{-1}≡1(mod) (m)),即转换为同余方程求解。特别的，当(m)为质数时，可以用费马小定理求解

(O(n))求解(1) ~ (n(mod) (p))的逆元
假设(p=k*i+r,k<i),我们尝试用(k^{-1})求(i^{-1})
(k*i+p≡0(mod) (p))
(Rightarrow k*i≡-r(mod) (p))
(Rightarrow k*i*i^{-1}*r^{-1}≡-r*r^{-1}*i^{-1} (mod) (p))
(Rightarrow -k*r^{-1}≡i^{-1} (mod) (p))
(Rightarrow i^{-1}≡-lfloor p/i floor *(p) (mod) (i)^{-1} (mod) (p))

其实，这本质上是利用了逆元也是积性函数的性质。
参考代码：

#include <cstdio>
#define ll long long
const int N=3000010;
ll n,p,inv[N];
int main()
{
    scanf("%lld%lld",&n,&p);
    inv[1]=1;printf("1
");
    for(int i=2;i<=n;i++)
    {
        inv[i]=((inv[p%i]*(p-p/i))+p)%p;
        printf("%lld
",inv[i]);
    }
    return 0;
}

(O(n))求解(1!)~(n!)的逆元（(p)为质数）
设第(i)项阶乘为(f_i),则有(f_i=i*f_{i-1})
若已经求得({f_i}^{-1})
则有(i*{f_{i-1}}*{f_i}^{-1}≡f_{i-1}*{f_{i-1}}^{-1} (mod p))
化简得 (f_{i-1}^{-1}≡i*{f_i}^{-1} (mod p))

参考代码：

void getinv()
{
    inv[0]=1;
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=(fac[i-1]*i)%mod;
    inv[n]=quick_pow(fac[n],n-2);
    for(int i=n-1;i;i--)
        inv[i]=(inv[i+1]*(i+1))%mod;
}

(6)中国剩余定理（孙子定理）

求解一次同余方程组，其中(m_1,m_2,...m_n)两两互质

[egin{equation} left{ egin{aligned} x ≡ b_1 (mod m_1) \ x ≡ b_2 (mod m_2) \ ... \ x ≡ b_n (mod m_n) \ end{aligned} ight. end{equation} ]

方法：先找到整数(L_1),使得(L_1≡1(mod m_1),b_1|L_1,b_2|L_1,...,b_n|L_1)
即(L_1)是同余方程

[egin{equation} left{ egin{aligned} x ≡ 1 (mod m_1) \ x ≡ 0 (mod m_2) \ ... \ x ≡ 0 (mod m_n) \ end{aligned} ight. end{equation} ]

的解。

把(L_1)乘上(b_1),即满足了第一个方程，而其余无影响。

然后找到(L_2,...,L_n).
(x=prod_{i=1}^n L_i)即为同余方程的解。

下面讨论如何得到(L_i)。
令(M=prod_{i=1}^n m_i)，设(M_i=M/m_i)
则(M_i)满足整除除了(b_i)的所有(b)

然后我们要求(L_i≡1(mod b_i))
设(M_i*t_i≡1(mod b_i))
即转换为了求解一次同余方程的问题。

我们对同余方程组进行(n)次同余方程的求解即可。

解为
(x≡prod_{i=1}^n M_i*t_i*b_i (mod M))

参考代码：中国剩余定理

四、组合计数

(1)加法原理与乘法原理

加法原理：做一件事，完成它可以有(n)类办法，在第一类办法中有(m_1)种不同的方法，在第二类办法中有(m_2)种不同的方法，……，在第(n)类办法中有(m_n)种不同的方法，那么完成这件事共有(N=sum{i=1}^n m_i)种不同方法。每一种方法都能够直接达成目标。

乘法原理：做一件事，完成它需要分成(n)个步骤，做第一步有(m_1)种不同的方法，做第二步有(m_2)种不同的方法，……，做第(n)步有(m_n)种不同的方法，那么完成这件事共有(N=prod_{i=1}^n m_i)种不同的方法。

(2)排列组合

从(n)个互异元素中依次取出(m)个元素存在顺序的排除一列，产生的不同排列的数量是
(A_n^m=n*(n-1)*(n-2)*...*(n-m+1)=frac{n!}{(n-m)!})

从(m)个互异元素中取出m个元素组成一个集合不存在顺序，产生的不同组合的数量是
(C_n^m=frac{A_n^m}{m!}=frac{n!}{m!(n-m)!})

考虑取出(m)个元素会产生(m!)种顺序

组合数的性质
①(C_n^m=C_n^{(n-m)})
感性证明：从集合中取出了(m)个元素就剩下了(n-m)个元素，方案数是相等的
②(C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1})（杨辉三角）
这一点十分重要，由此可以得出组合数的递推式。
感性证明：现在已经取到了第(n)个元素。我们有两个选择，取第(n)个元素或不取第(n)个元素
若取第(n)个元素，则先在前(n-1)个元素中取(m-1)个，为(C_{n-1}^{m-1})
若不取第(n)个元素，则先在前(n-1)个元素中取(m)个，为(C_{n-1}^m)
根据加法原理，可以得到(C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1})
③(sum{i=0}^n C_n^i=2^n)
感性证明：从(n)个互异元素中取出若干个组成一个集合，有(n+1)种方法，分别取出0,1,..n个元素，又由加法原理，有(sum{i=1}^n)种方法
从另一种角度看，每个元素在原集合里都有两种情况，取或不取，方案数为(2^n)

以上也可以代入计算式进行验证。

组合数的求法
①用第二个性质，可以在(O(n^2))求出0<=j<=i<=n的所有组合数(C_i^j)

void get()
{
    C[1][1]=1;
    for(int i=2;i<=N;i++)
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}

②用计算式在(O(nlogn))求出某一个组合数(C_i^j)
因为结果一般较大，通常会用mod取一下模
所以先求出分母(m!(n-m)!)的逆元

void getinv()
{
    inv[0]=1;
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=(fac[i-1]*i)%mod;
    inv[n]=quick_pow(fac[n],n-2);
    for(int i=n-1;i;i--)
        inv[i]=(inv[i+1]*(i+1))%mod;
}
int get(int i,int j)
{
    return (fac[i]*inv[j]*inv[i-j])%mod;
}

(3) 二项式定理

((x+y)^n=sum_{i=0}^n C_n^i*a^i*b^{n-i})
这个其实手玩一下就出来了，用排列组合的思想考虑每一项出现的次数。
下面证明(Lucas)定理要用到

(4) (Lucas) 定理

若(p)是素数，则有
(C_n^m≡C_{n\%p}^{m\%p}*C_{n/p}^{m/p} (mod p))

证明：
首先素数的条件用在这个地方
当(p)为质数时，任取(x in (1,p)且x in N),满足(C_p^x≡0 (mod p))。这点不难，不证明了。

设(n=ap+r_1,m=bp+r_2)

取((1+x)^n%p)这样一个式子，我们对它进行变形（本质上对应将数进行p进制分解）

((1+x)^n=(1+x)^{ap+r_1}=((1+x)^p)^a*(1+x)^{r_1})
(≡(1+x^p)^a*(1+x)^{r_1}=sum_{i=0}^a C_a^i*x^{i*p}*sum C_{r_1=0}^j*x^j (mod p))(注意最后两步用了二项式定理化简，第三步用了那个没证明的玩意儿)

整理得((1+x)^n≡sum_{i=0}^a C_a^i*x^{i*p}*sum C_{r_1=0}^j*x^j (mod p))

对左边这样一项(x^{bp+r_2})来说，它的系数为(C_{ap+r_1}^{bq+r_2})

而右边当且仅当(i=b,j=r_2)时，可以构成这个项，而它的系数为(C_a^b*C_{r_1}^{r_2})

即(C_n^m≡C_{n\%p}^{m\%p}*C_{n/p}^{m/p} (mod p))，则得证

咕咕咕

开始更新组合数学 2018.6.29