知识汇总-数论

质数,约数(反素数,除法分块),欧拉函数,同余(费马小,欧拉定理,欧拉降幂,exgcd,中国剩余定理,乘法逆元,线性同余方程,高次同余方程),矩阵快速幂,高斯消元,线性空间(生成子集,线性相关和线性无关,基底,矩阵的秩,线性基),组合数(二项式定理,多重集的排列数和组合数,卢卡斯定理,卡特兰数),容斥原理(多重集组合数),莫比乌斯函数(莫比乌斯反演),概率与数学期望,0/1分数规划,博弈论之SG函数(NIM博弈,公平组合游戏)

质数

  • 对于一个足够大的整数N,不超过N的质数大约有N/lnN个;
  • 求出L,R(1<=L<=R<=2^31,R-L<=1e6)之间相邻两个质数的差的最大值是多少。解:筛出2~sqrt(R)间所有的素数,用这些素数筛掉[L,R]之间的合数,然后扫描即可。
  • 将N!分解质因数。解:N!的每个质因子都不会超过N,将每个质因子p筛出来,然后考虑阶乘N!中有多少个质因子p。N!中p的个数就等于1~N中每个数包含p的个数之和。含一个p的就是N/p个,两个p的就是N/p^2个,因为在统计2个的时候已经统计过一个的,所以直接加上即可。所以p的因子个数为N/p+N/p^2+...+N/p^(lgN/lgp)个,枚举每个因子即可。

约数

定理

  • 若正整数N被唯一分解为N=p1^c1*p2^c2*...*pm^cm,则N的正约数集合可写作:{p1^b1*p2^b2*p3^b3*...*pm^bm},其中0<=bi<=ci;
  • N的正约数个数为(c1+1)*(c2+1)*...*(cm+1);
  • N的所有正约数的和为(1+p1+p1^2+...+p1^c1)*(1+p2+p2^2+...+p2^c2)*(1+p3+p3^2+...+p3^c3)*...*(1+pm+pm^2+...+pm^cm);
  • 一个整数N的约数个数上届为2sqrt(N)。
  • 1~N中每个数的约数个数的总和大约为NlgN。

反素数

  • 对于任何正整数x,其约数个数记为g(x)。如果对于任意的0 < i < x,都有g(x)>g(i),那么x称为反质数。现给定一个数N(1<=N<=2e9),求不超过N的最大反质数x。
  • 引理1: 1~N中最大的反质数,就是1~N中约数个数最多的数中最小的一个;
  • 引理2:1~N中任何数的不同质因子都不会超过10个,且所有质因子的指数综合不超过30;
  • 引理3:x的质因子是连续的若干个最小的质数,且指数单调递减
  • dfs尝试一次确定前10个质数的指数,并满足单调递减,总乘积不超过N,同时记录约数个数即可(以上证明详见《算法竞赛进阶指南》P140)。
  • 余数之和:给定正整数n和k,求(kmod1)+(kmod2)+(kmod3)+…+(kmodn)的值。(1<=n,k<=1e9).
  • 转化为n*k-∑(k/i)i
  • 除法分块,对于任意i∈[1,k],k/i的值不超过2*sqrt(k)个。对于每一块最左边的元素x,与之同一块的最大元素为g(x)=k/(k/x).
  • 故上式对于每一块中的(k/i)*i=(k/x)*i,是[x,g(x)]的以(k/x)为公差的等差数列,整个式子∑(k/i)*i就是对每一块进行等差数列求和。

欧拉函数

同余

基本概念

  • 同余类:同一个集合中所有数模m同余,称他们为一个模m的同余类
  • 完全剩余系:模m的同余类一共有m个,他们构成m的完全剩余系
  • 简化剩余系:1~m中与m互质的数代表的同余类共有φ(m)个,他们构成m的简化剩余系。简化剩余系关于m乘法封闭,即如果a,b属于简化剩余系,则axb也属于简化剩余系。

费马小定理

  • 若p是质数,对于任意整数a,有a^p≡a(mod p);

欧拉定理

  • 若正整数a,n互质,则a^φ(n)≡1(mod p),其中φ(n)为欧拉函数.

欧拉定理的推论(欧拉降幂)

  • 当正整数a,n互质,对于任意正整数b,a^b≡a^(b mod φ(n)) (mod n)
  • 当a,n不互质且b>φ(n)时,有a^b≡a^(b mod φ(n) + φ(n)) (mod n)

扩展欧几里得

对于任意整数a,b,存在一对整数x,y,满足ax+by=gcd(a,b)。

  • 当b=0时,显然有一对整数x=1,y=0,使得a*1+0*0=gcd(a,0);
  • 当b>0,则gcd(a,b)=gcd(b,a mod b)。假设存在一对整数x,y,满足b*x+(a mod b)*y=gcd(b,a mod b),因为bx+(a mod b)y=bx+(a-b(a/b))y=ay+b(x-(a/b)y),所以令x’=y,y’=x-(a/b)y,就得到了ax’+by’=gcd(a,b)。
  • 对于更为一般的方程ax+by=c,它有解当且仅当d|c。我们先求出ax+by=d的一组特解x0,y0,然后同时乘上c/d,就得到了ax+by=c的一组特解(c/d)x0,(c/d)y0。
    • 事实上,方程ax+by=c的通解可以表示为x=(c/d)x0+k(b/d),y=(c/d)y0-k(a/d) (k∈Z)。
    • 其中k取遍整个整数集合,d=gcd(a,b),x0,y0是ax+by=gcd(a,b)的一组特解。

中国剩余定理

  • 对于形如x≡ai(mod mi)的方程组,x=∑aiMiti,其中Mi为除mi外所有模数的倍数,ti是线性同余方程Miti≡1(mod mi)的一个解。
    1
    2
    3
    4
    5
    6
    7
    LL exgcd(LL a,LL b,LL &x,LL &y) 
    {
    if(b==0){x=1,y=0;return a;}
    LL d=exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-y*(a/b);
    return d; //返回值为gcd(a,b)
    }

乘法逆元

乘法逆元

线性同余方程

  • 给定整数a,b,m,求一个整数x满足ax≡b(mod m),或者给出无解。
  • ax≡b(mod m)等价于求a·x-b是m的倍数,不妨设为-y倍。于是该方程可改写为a·x-b=-y·m,即a·x+m·y=b,可以用扩欧求解。
  • 此线性同余方程有解当且仅当gcd(a,m)|b。
  • 在有解时,用扩欧求出一组整数x0,y0,满足a·x0+m·y0=gcd(a,m),然后x=x0*b/gcd(a,m)就是原线性同余方程的一个解。
  • 方程的通解是所有模m/gcd(a,m)与x同余的整数。
  • 例题:同余方程

高次同余方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int baby_step_giant_step(int a,int b,int p){
map<int,int> Hash;Hash.clear();
b%=p;
int t=(int)sqrt(p)+1;
for(int j=0;j<t;j++){
int val=(long long)b*power(a,j,p)%p;//b*a^j
Hash[val]=j;
}
a=pow(a,t,p);//a^t
if(a==0) return b==0?1:-1;
for(int i=0;i<=t;i++){
int val=power(a,i,p);//(a^t)^i
int j=Hash.find(val)==Hash.end()?-1:Hash[val];
if(j>=0 && i*t-j>=0) return i*t-j;
}
return -1;
}

矩阵快速幂

  • 构造方式:把长为n的一维向量称为“状态矩阵”,把用于与“状态矩阵”相乘的固定不变的矩阵A称为“转移矩阵”。若状态矩阵中的第x个数对下一单位时间状态矩阵中的第y个数产生影响,则把转移矩阵的第x行第y列赋予适当的系数。时间复杂度为O(n^3logT),其中n为状态矩阵长度(一般不会很大),T为递推次数。
  • 以下情况可以考虑用矩阵快速幂优化。
    • 可以抽象出一个长度为n的一维向量,该向量在每个单位时间发生一次变化。
    • 变化的形式是一个线性递推(只有若干“加法”或“乘一个系数”的运算)。
    • 该递推是在每个时间可能作用于不同的数据上,但本身保持不变。
    • 向量变化时间(即递推次数)很长,但向量长度n不大。
  • 例题:H
    取石头

高斯消元

  • 将增广矩阵化为简化阶梯形矩阵求解线性方程组。
  • 步骤:
    • 将a[][i]最大的一行放到第i行
    • 将a[i][i]化为1,整行除以a[i][i]
    • 将a[i][i]下面一整列化为0
    • i取[1,n]
    • 上三角矩阵完成后,倒回去求每一项的值
  • 若高斯消元后,存在系数全为0,常数不为0的行,则方程无解;若系数不全为0的行恰好有n个,则说明主元有n个,方程组有唯一解;若系数不全为零的行有k < n个,则说明主元有k个,自由元有n-k个,方程组有无穷多个解。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35

    int gauss(){
    int t,r=0;
    rep(i,1,n){
    t=i;
    //找到a[][i]!=0
    rep(k,i,n)
    if(a[k][i] > eps){
    t=k;
    break;
    }
    if(t!=i) swap(a[i],a[t]);
    if(fabs(a[i][i]) < eps) continue;
    //a[i][i]化为1
    repd(j,n+1,i) a[i][j]/=a[i][i]; // 倒序
    //a[i][i]左下角化为0
    rep(k,i+1,n){
    if(fabs(a[k][i]) < eps)continue;
    repd(j,n+1,i) //倒序
    a[k][j] -= a[k][i]*a[i][j];
    }
    r++
    }
    if (r < n){
    for (int i = r; i < n; i ++ )
    if (fabs(a[i][n+1]) > eps)
    return 2; // 无解
    return 1; // 有无穷多组解
    }
    //不用把右上角全化为0,更新答案即可
    repd(i,n,1)
    repd(j,i-1,1)
    a[j][n+1] -= a[j][i] * a[i][n+1];
    return 0;
    }
  • 具体写法

线性空间

生成子集

  • 给定若干个a1,a2,a3….ak,若向量b能由它们经过向量加法和标量乘法表示,称向量b能被a1,a2…ak张成。显然,a1,a2…an能张成出的所有向量构成一个线性空间,a1,a2…ak被称为这个线性空间的生成子集。

线性相关与线性无关

  • 任意选择出线性空间中的若干个向量,如果其中存在一个向量能被其他向量张成,则这些向量线性相关,否则称这些向量线性无关。

基底

  • 线性无关的生成子集被称为线性空间的基底,简称基。基的另一种定义是线性空间的极大线性无关子集。一个线性空间的所有基包含的向量个数都相等,这个数被称为线性空间的维数。

矩阵的秩

  • 所有行向量能张成的所有向量构成一个线性空间,这个线性空间的维数被称为矩阵的“行秩”,同理我们可以知道“列秩”,显然行秩等于列秩,都被称为矩阵的秩。在高斯消元后,显然简化阶梯形矩阵的所有非零行向量线性无关。于是,简化阶梯形矩阵的所有非零行向量就是该线性空间的一个基,非零行向量的个数就是矩阵的秩

线性基

  • 这里特指异或空间的基。即给定一个线性空间,求出线性基后就可表示出这个线性空间所有的元素。
  • 给定n个0~2^m-1个整数a1,a2…an,如何求他们的线性基?我们把每个数看成m位二进制数,写成一个n行m列的01矩阵,矩阵中第i行从左到右依次是ai的第m-1,m-2…1,0位(二进制最低位)。把矩阵高斯消元即可。
  • 具体求法:起初简化阶梯矩阵想x[]为全0,x[i]表示矩阵中第一个令在第i位的元素,每插入一个数ai时,扫描ai的二进制位k,如果第k位所对应的列没有元素,则令x[k]=ai;如果第k列有元素,则令ai^=x[i],然后继续扫描ai后面的二进制位。
  • 显然,ai进行插入操作后,要么进入线性基,要么被异或为0,说明已经可以被基中向量张成。证明:x1^x2…^xm=ai => x1^x2^…^xm^ai=0。
  • 得到线性基后,假如线性基大小为t,那么我们可以用这些元素张成出2^t个去重异或集合,这个集合也是原异或空间选择任意个向量能张成出的最大集合(不包括0)。此外,不去重异或集合中,每个数出现2^(n-t)次。其中,最大的异或和就是将线性基中所有位都异或起来得到的结果,而最小的异或和就是线性基中的最后一个非零元素或0。
    当t < n时异或空间可异或出0
  • 异或和第k小:若异或空间可异或出0,那么我们要求低k-1小的元素,因为线性基无法张成0。我们把k-1进行二进制分解,如果k-1的第j位等于1,就选取x[t-j],最后选出的x异或起来就得到了答案。特别的,若k>2^t,则无解。
  • 例题

组合数

组合数

莫比乌斯函数

  • 将N分解质因数N=p1^c1·p2^c2·p3^c3…pm^cm。当N包含相等的质因子时,μ(N)=0;当N的所有质因子各不相同时,若N有偶数个质因子,μ(N)=1,若N有奇数个质因子,μ(N)=-1。
  • 若只求一项莫比乌斯函数,则分解质因数即可计算。若求1~N的每一项莫比乌斯函数,可以用埃拉托斯特尼筛法计算:把所有μ值初始化为1。接下来,对于筛出的每个质数p,令μ(p)=-1,并扫描p的倍数x=2p,3p,…(n/p)·p,检查x能否被p^2整除。若能,则令μ(x)=0,否则令μ(x)=-μ(x)。
  • 莫比乌斯反演:若g(x)=∑f(d),其中x|d,则f(x)=∑μ(d/x)*g(d),其中x|d
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(int i=1;i<=n;i++) miu[i]=1,v[i]=0;
    for(int i=2;i<=n;i++){
    if(v[i]) continue;
    miu[i]=-1;
    for(int j=2*i;j<=n;j+=i){
    v[j]=i;
    if((j/i)%i==0) miu[j]=0;
    else miu[j]*=-1;
    }
    }

概率与数学期望

  • 期望的定义:如果X是一个离散的随机变量,输出值为x1,x2…,其输出值相应的概率为p1,p2…(概率和为1),那么期望值 。如:掷一个骰子的期望E(x)=(1+2+3+4+5+6)/6=3.5。
  • 数学期望是线性函数,满足;当两个随机变量X和Y独立且各自有自己一个已定义的期望时,有。掷两个骰子的点数可以表示为随机变量2X,于是E(2x)=2E(x)=7;
  • 全概率公式:假设是一个概率空间的有限或者可无限的分割,且每个集合是一个可测集合,则对于任意事件A有全概率公式:其中P(A|B)是在B发生的前提下A发生的概率。$P(A|B) = P(AB)/P(B)$。
  • 全期望公式:其中P表示概率,表示X为时Y的期望。

0/1分数规划

  • 给定整数a1~an和b1~bn,求一组解xi(1 <= i <= n),使最大化。即个特定n对整数ai,bi,从中选出若干对,使选出的数对的a之和与b之和商最大。
  • 实数域二分答案(商)。check方式:
    • 对于当前答案ans,如果存在一组解,使得,即,则有比ans更大的答案满足条件,令l=mid,否则令r=mid。
    • 因为每一组的可直接算出来,所以我们只需要将所有的正值加起来就可以取得最大值,若最大值满足上述条件,则存在更优解。

博弈论与SG函数

巴什博弈

  • 有n个石子,两个人轮流从中取走一部分,每人每次至少1个,至多m个,无法取石子的人败,问是否先手必胜。
    • 若n%(m+1)!=0,先手必胜;否则先手必败
    • 若n = k*(m+1) + r, 先手取掉r个,无论后手怎么取,先手都能使剩下的石子数%(m+1)==0,也就是后手没有一次取完的可能。

威佐夫博弈

  • 有数量分别为a,b的两堆石子,两个人轮流从中取走一部分,每个人每次有两种取法:1. 在其中一堆取走任意数量石子 2. 同时在两堆中取走相同数量石子。最后无法取石子的人败,能否先手必胜。
    • 假设a和b中大的是a,若,则先手必胜。
    • 奇异(先手必败)局势有:(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18) …….

NIM博弈

  • 给定n堆物品,第i堆中有Ai个物品,两名玩家轮流行动,每次从某一堆中取走若干个物品,可以全拿,但是不能不拿。拿走最后一件物品者获胜,两人取最优策略,问能否先手必胜。
    • 先手必胜,当且仅当A1 xor A2 xor A3… xor An 不为0。
    • 证明:如果A1 xor A2 xor…xor An=x!=0,设x的二进制位表示下最高位的1在第k位,那么至少存在一堆石子Ai,它的第k位是1。显然Ai xor x < Ai,从Ai中拿走一部分石子,使得Ai=Ai xor x,就得到了一个各堆石子数异或和为0的局面。对于任意一个石子数异或和为0的局面,无论怎么拿,异或和都不等于0,即必败。另外,令所有满足Ai xor x < Ai的Ai的集合为B,先手第一步在集合B中取任意一个,都能使得先手必胜。

公平组合游戏ICG

  • 若一个游戏满足一下条件则称其为公平组合游戏。上诉三种博弈属于公平组合游戏。
    • 由两名玩家交替行动
    • 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关
    • 不能行动的玩家判负

有向图游戏

  • 给定一个有向无环图,图中有唯一起点,在起点上放一枚棋子。两名玩家交替地把这枚棋子沿着有向边进行移动,每次可以移动一步,无法移动者负。任何一个公平组合游戏都可以转化为有向图游戏。具体方法:把每个局面看成图中的一个节点,并且每个局面沿着合法行动能到达的下一个局面连有向边。

Mex运算

  • 设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算。

SG函数

  • 在有向图游戏中,对于每个节点x,设从x出发共k条有向边,分别到达节点y1,y2,y3…yk,定义SG(x)为x的后继节点y1,y2…yk的SG函数值构成的集合再执行mex运算的结果,即:SG(x)=mex({SG(y1),SG(y2)...SG(yk)})。整个有向图G的SG函数值被定义为有向图游戏起点s的SG函数值,即SG(G)=SG(s)。

有向图游戏的和

  • 设G1,G2…Gm是m个有向图游戏。定义有向图游戏G,它的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步。G被称为有向图游戏G1,G2,G3…Gn的和。有向图游戏的和的SG函数值等于它包含的各个字游戏SG函数值得异或和,即:SG(G)=SG(G1) xor SG(G2)...xor SG(Gm)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void initSG(int n){
    memset(sg,0,sizeof(sg));
    for(int i=1;i<=n;i++){//当前堆中有i个石头
    memset(Hash,0,sizeof(Hash));
    for(int j=1;f[j]<=i;j++)
    Hash[sg[i-f[j]]]=1;
    int t=0;
    while(Hash[t]) t++;
    sg[i]=t;
    }
    }

一般博弈的求解

  • 状态表示
  • 寻找必败态
    • 手推小数据——>猜想——>证明
    • 证明判定是否满足以下性质:
      • 末状态为必败态
      • 任何一个胜态都有策略变成必败态
      • 任何一个必败态都无法变成另一个必败态
  • 将其他局面转化为必败态
  • 在当前局面,只要有一个决策使得下一局面为必败态,当前局面就是必胜态。在数据较小时可以利用这个原理进行记忆化搜索。
Donate comment here