[关闭]
@Bei-S 2019-02-14T06:31:15.000000Z 字数 3673 阅读 635

基础数论

数论


所谓万丈深渊,下去,也是前程万里。——木心

这部分内容比较枯燥,但非常重要,自己仔细推一下!!!


计数原理

加法原理

如果事件A有p种生产方式,B有q种生产方式,则事件(A或B)有(p+q)种生产方式
注意:事件A和事件B产生的方式不重合

乘法原理

如果事件A有p种生产方式,B有q种生产方式,则事件(A与B)有(p*q)种生产方式
注意:事件A和事件B必须互相独立
加法原理和乘法原理都可以推广到n个事件使用

容斥原理

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。

抽屉原理(鸽巢原理)

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。


二项式定理

此处输入图片的描述
其中每个 此处输入图片的描述为一个称作二项式系数的特定正整数,其等于 此处输入图片的描述 。这个公式也称二项式公式或二项恒等式。使用求和符号,可以把它写作


快速幂&&快速乘

快速幂:

  1. ll qpow(ll a,ll b){
  2. ll ans=1;
  3. while(b){
  4. if(b&1) ans*=a;
  5. a*=a;
  6. b>>=1;
  7. }
  8. return ans%k;
  9. }

快速乘:

  1. inline ll Mul(ll a,ll b){
  2. int ret=0;
  3. while(b){
  4. if(b&1) ret+=a;
  5. a+=a;
  6. b>>=1;
  7. }
  8. return ret;
  9. }

扩展欧几里得

唯一分解定理

任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积。
比如,1260=2*2*3*3*5*7

费马小定理

p为素数,a为正整数,a与p互质,则 a^(p-1)≡ 1 (mod p) 。

欧拉小定理

a^φ(m) ≡ 1 (mod m),(a与m互质) 。
欧拉函数 φ(m)
φ(m)表示不超过m的与m互质的数的个数。

裴蜀定理

若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
推广:n个整数,a1,a2,a3......an为n个整数,d是它们的最大公约数,那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。

素数筛

A.埃氏筛法:只需要把所有的 2 的倍数,3 的倍数,…… 都排除掉那么剩下的都是素数
时间复杂度
考虑优化:我们只让每个合数被它的最小质因子筛去,就能保证复杂度是
B.线性筛

  1. inline void pre(){
  2. vis[0]=vis[1]=1;
  3. for(int i=2;i<=n;i++){
  4. if(!vis[i]) pri[++cnt]=i;
  5. for(int j=1;j<=cnt&&pri[j]*i<=n;j++){
  6. vis[pri[j]*i]=1;
  7. if(i%pri[j]==0) break;
  8. }
  9. }
  10. }

欧几里得算法(辗转相除)

引理:
证明:设a=p*b+r,r=a%b,c=gcd(a,b)
设a=x*c,b=y*c,其中x,y互质
r=a-p*b=x*c-p*y*c=(x-p*y)*c
当y与x-p*y互质时,gcd(b,r)=c
证明互质:
假设不互质,设y=n*k,x-p*y=m*k,且k>1(n,m互质)
所以 x-p*n*k=m*k
x=k*(m+n*p)
则a=x*c=k*(m+n*p)*c,b=n*k*c
此时gcd(a,b)=kc,与原命题矛盾
故y与x-p*y互质得证
当a%b==0时,gcd(a,b)=b

扩展欧几里得(exgcd)

用于求解不定方程,线性同余方程,逆元
引理:存在x,y使得gcd(a,b)=a*x+b*y
证明:b=0时,gcd(a,b)=b,x=0,y=1
b!=0时,设a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2
因为a%b=a-a/b*b
所以 a*x1+b*y1=b*x2+(a-a/b*b)*y2
a*x1+b*y1=a*y2+b*(x2-a/b*y2)
x1=y2,y1=x2-a/b*y2
所以递推可得第一组解

  1. int exgcd(int a,int b,int &x,int &y){
  2. if(b==0){
  3. x=1;
  4. y=0;
  5. return a;
  6. }
  7. int g=exgcd(b,a%b,x,y);
  8. int t=x;
  9. x=y;
  10. y=t-a/b*y;
  11. return g;
  12. }

解不定方程/线性同余方程:
参考exgcd详解

逆元

首先说明逆元的概念,类似于倒数的性质。

方程ax≡1(mod p),的解称为a关于模p的逆,当gcd(a,p)==1(即a,p互质)时,方程有唯一解,否则无解。
对于一些题目会要求把结果MOD一个数,通常是一个较大的质数,对于加减乘法通过同余定理可以直接拆开计算,但对于(a/b)%MOD这个式子,是不可以写成(a%MOD/b%MOD)%MOD的,但是可以写为(a*b^-1)%MOD,其中b^-1表示b的逆元。

求法

A. 费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理,在1636年提出,其内容为: 假如p是质数,且gcd(a,p)=1,那么 a(p-1)≡1(mod p),即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。

意思很明了,由上方的公式很容易推导出:a*a(p-2)≡1(mod p)对于整数a,p,a关于p的逆元就是a^(p-2),直接快速幂解之即可,但注意这个定理要求a,p互质!

  1. inv[i]=qpowip-2
B.线性递推
  1. inv[1] = 1;
  2. for(i=2;i<M;++i) inv[i]=(M-M/i)*inv[M%i]%M;

首先我们有一个

放到%M意义下得
同时乘上 得到

C.exgcd

因为
所以可以写作
gcd(a,p)=1
求解即可


组合数问题

排列问题

从n个不同的元素中,取r个不重复的元素,按次序排列,称为从n个中取r个的无重排列。排列的全体组成的集合用 A(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为 A(n,r)。

n个数,k个位置,多少排列方法?

组合问题

n个不同元素中取r个不重复的元素组成一个子集,而不考虑其元素的顺序,称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示,对应于可重组合C(n,r)

n个数,k个位置,多少排列方法(顺序无关)?

组合数性质

对于0≤r≤n,有C(n,r)=C(n,n-r)

C(n,r)=C(n-1,r)+C(n-1,r-1)

C(n,0)+C(n+1,1)+C(n+2,2)+ …+C(n+r,r)=C(n+r+1,r)

C(n,l)*C(l,r)=C(n,r)*C(n-r,l-r)

C(n,0)+C(n,1)+…+C(n,n-1)+C(n,n)=2n

C(n,0)-C(n,1)+C(n,2)-…±C(n,n)=0

C(m+n,r)=C(m,0)*C(n,r)+C(m,1)*C(n,r-1)+…+C(m,r)*C(n,0)

C(m+n,m)=C(m,0)*C(n,0)+C(m,1)*C(n,1)+…+C(m,m)*C(n,m)

错排

n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排;有的叫重排。
递推公式
此处输入图片的描述

组合数逆元


中国剩余定理

中国剩余定理


欧拉函数

在数论中,对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数,记作φ(n)。

 φ函数的值:

φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x

的所有质因数;x是正整数; φ(1)=1(唯一和1互质的数,且小于等于1)。注意:每种质因数只有一个。

 例如:

     φ(10)=10×(1-1/2)×(1-1/5)=4;

     1 3 7 9

     φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

     φ(49)=49×(1-1/7)=42;

卡特兰数,斯特林数

卡特兰数
斯特林数


矩阵


概率期望

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注