数论

By Angela Balzac in 2018

费马小定理

若p是质数，a是任意整数，并且a不能被p整除，于是：
$a^{p-1}≡1(mod \ p)$

欧拉函数

OEIS A000010

φ(n)表示1~n以内和n互质的数的个数。
p表示n的所有质因数。
有$φ(n)=n*\prod_{p|n}^p\ (1-\frac{1}{q})$

• 欧拉函数是积性函数，若m,n互质，则：$φ(mn)=φ(n)*φ(m)$
• 若n为奇数，则：$φ(2n)=φ(n)$
• 若n为质数，则：$φ(n)=n-1$

线性筛欧拉函数

int m[maxn],phi[maxn],p[maxn],pt;//m[i]是i的最小素因数，p是素数，pt是素数个数
int get_phi(){
    phi[1]=1;
    int N=maxn,k;
    for(int i=2;i<N;i++){
        if(!m[i]){//i是素数
            p[pt++]=m[i]=i,phi[i]=i-1;
        }
        for(int j=0;j<pt&&(k=p[j]*i)<N;j++){
            m[k]=p[j];
            if(m[i]==p[j]){//为了保证以后的数不被再筛，要break
                phi[k]=phi[i]*p[j];
/*这里的phi[k]与phi[i]后面的∏(p[i]-1)/p[i]都一样（m[i]==p[j]）只差一个p[j]，就可以保证∏(p[i]-1)/p[i]前面也一样了*/
                break;
            }
            else{
                phi[k]=phi[i]*(p[j]-1);//积性函数性质
            }
        }
    }
}

欧拉定理

若$gcd(a,b)=1$，则：$a^{φ(b)}≡1(mod \ b)$

更常用的：$a^b \% m=a^{b \% φ(m)+φ(m)}\%m$

原根

定义：设m>1，$gcd(a,m)=1$，使得$a^r≡1(mod \ m)$成立的最小的r，称为a对模m的阶，记为$\delta_m(a)$。

数m有原根的充要条件：$m=2,4,p,2p,p^k$ (p为奇素数，k为任意正整数)。

定理

• 如果模m有原根，那么它一共有$φ(φ(m))$个原根。
• 若m>1，$gcd(a,m)=1$，$a^n≡1(mod \ m)$，则$\delta_m(a)|n$。
• 如果p为素数，那么素数p一定存在原根，并且p模的原根的个数为$φ(p-1)$。
• 设m是正整数，a是整数，若a模m的阶等于$φ(m)$，则称a为模m的一个原根。

找原根

若欲求m的原根的话,对$φ(m)$进行质因数分解，求出所有质因子$p_i$，若对于任意$p_i$，均满足$g^{\frac{φ(m)}{p_i}}\neq 1(mod \ m)$，则g是m的原根。

求原根的代码

#include<bits/stdc++.h>
using namespace std;
int p[100007], c;
long long pow_mod(long long a,long long x,long long m){
    long long ans=1;
    while(x){
        if(x&1){
            ans=ans*a%m;
        }
        a=a*a%m;
        x>>=1;
    }
    return ans;
}
bool ok(int x,int ph,int m){
    for(int i=0;i<c;i++){
        if(pow_mod(x,ph/p[i],m)==1){
            return 0;
        }
    }
    return 1;
}
void divide(int x){
    c=0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            p[c++]=i;
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1){
        p[c++]=x;
    }
}
int main(){
    int wxh;
    scanf("%d",&wxh);
    while(wxh--){
        int n;
        scanf("%d",&n);
        int m=n,ans=m;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                ans=ans/i*(i-1);
                while(n%i==0){
                    n/=i;
                }
            }
        }
        if(n>1){
            ans=ans/n*(n-1);
        }
        divide(ans);
        int x=ans;
        while(!ok(x,ans,m)){
            x--;
        }
        printf("%d\n",x);
    }
    return 0;
}

二次剩余

当存在某个x，式子$x^{2}≡d(mod\ p)$成立时，称“d是模p的二次剩余”。
当对任意x不成立时，称“d是模p的二次非剩余”。
学不来
关于如何计算二次剩余，详见Miskcoo的博客

解方程a^b≡n(mod p)(p是素数)

一、已知n,p(p是奇数),b=2,求a

由费马小定理：$n^{(p-1)/2}≡\pm1(mod\ p)$
根据欧拉准则,二次剩余有解当且仅当$n^{(p-1)/2}≡1(mod\ p)$
如果c满足$w=c^2-n$不是p的二次剩余，那么$a=(c+\sqrt(w))^{(p-1)/2}$是方程$a^2≡n(mod\ p)$的解。因为有一半的数是非二次剩余，所以可以随机c，验证即可。
详见Philipsweng的博客

二、已知n,p,a,求b

使用Baby-step giant-step算法
(临时)详见Yuiffy的博客

模板(Poj 2417)

#include<bits/stdc++.h> 
using namespace std;
long long p,b,n;
void exgcd(long long c,long long d,long long &x,long long &y){
    if(!d){
        x=1;y=0;
        return ;
    }
    exgcd(d,c%d,x,y);
    long long z=y,r=x-(c/d)*y;
    x=z;y=r;
}
void work(){
    long long m=(long long)sqrt(p),bb=1,nn=n,inv,t;
    map<int,int> num;
    map<int,bool> app;
    app[1]=1;
    num[1]=0;
    for(int i=1;i<=m-1;i++){
        bb=bb*b%p;
        if(!app[bb]){
            app[bb]=1;
            num[bb]=i;
        }
    }
    bb=bb*b%p;
    exgcd(bb,p,inv,t);
    if(inv>0){
        inv%=p;
    }
    else{
        inv=inv%p+p;
    }
    for(int i=0;i<=m;i++){
        if(app[nn]){
            printf("%lld\n",i*m+num[nn]);
            return;
        }
        nn=nn*inv%p;
    }
    printf("no solution\n");
}
int main(){
    while(~scanf("%lld%lld%lld",&p,&b,&n)){
        work();
    }
    return 0;
}

Ramsey定理

存在一个p，使得对p个点的完全图红蓝染色，要么存在n个点的红色完全子图，要么存在m个点的蓝色完全子图。
把最小的p记作R(n,m)，称为Ramsey数，一般用到R(3,3)=6。
更大的Ramsey数特别难算。

第一类Stirling数

OEIS A008275(有符号)

表示将n个不同元素构成m个圆排列的方案数。
通俗来说，就是n个不同人围m个相同圆桌而坐，要求各桌非空，其不同方案数。
第一类Stirling数又分为无符号($S_u$)与有符号($S_s$)两种。

无符号

递推式
$S_u(n+1,m)=S_u(n,m-1)+nS_u(n,m)$

性质
- $S_u(0,0)=1$
- $S_u(n,0)=0$
- $S_u(n,n)=1$
- $S_u(n,1)=(n-1)!$
- $S_u(n,n-1)=C(n,2)$
- $S_u(n,2)=(n-1)!\sum_{i=1}^{n-1}{\frac{1}{i}}$
- $S_u(n,n-2)=2C(n,3)+3C(n,4)$
- $\sum_{k=0}^n{S_u(n,k)}=n!$

有符号

递推式
$S_s(n+1,m)=S_s(n,m-1)-nS_s(n,m)$

性质

• $S_s(n,m)=(-1)^{n+m}*S_u(n,m)$
• $\sum_{k=0}^n{S_s(n,k)}=0^n (其中0^0=1)$

例子
有n个仓库，每个仓库有两把钥匙，共2n把钥匙。同时又有n位官员。问如何放置钥匙使得所有官员都能够打开所有仓库？（只考虑钥匙怎么放到仓库中，而不考虑官员拿哪把钥匙。）那如果官员分成m个不同的部，部中的官员数量和管理的仓库数量一致。那么有多少方案使得，同部的所有官员可以打开所有本部管理的仓库，而无法打开其他部管理的仓库？（同样只考虑钥匙的放置。）

第一问很经典，就是打开将钥匙放入仓库构成一个环：1号仓库放2号钥匙，2号仓库放3号钥匙……n号仓库放1号钥匙。这种情况相当于钥匙和仓库编号构成一个圆排列方案数是$(n-1)!$种。
而第二问就对应的将n个元素分成m个圆排列，方案数就是第一类无符号Stirling数$S_u(n,m)$ 。如要要考虑官员的情况，只需再乘上$n!$即可。

第二类Stirling数

OEIS A008277

表示将n个不同的元素拆分成m个集合的方案数。
通俗来说，就是将n个不同的球放入m个无差别的盒子中，要求盒子非空，求方案数。

公式
$S(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n$

递推式
$S(n+1,m)=S(n,m-1)+mS(n,m)$

性质

• $S(n,0)=0^n (其中0^0=1)$
• $S(n,1)=1$
• $S(n,n)=1$
• $S(n,2)=2^{n-1}-1$
• $S(n,n-1)=C(n,2)$
• $S(n,n-2)=C(n,3)+3C(n,4)$
• $\sum_{k=0}^n{S(n,k)}=B_n(B_n是贝尔数，后面有讲到)$

卡特兰数

OEIS A000108

应用

• n个节点的二叉树的个数
• n边形分成三角形的方案数
• n对括号合法序列数
• n个数出栈顺序方案数
• 平面上处于凸包上的2n个点两两连边，边不相交的方案数
• 在2*n的格子里填入1~2n这些值，每个格子比上边和右边的数都小的方案数

$cat(n)=\sum cat(i)cat(n-i-1)=\frac{(4n-2)cat(n-1)}{n+1}=\frac{C(2,2n)}{n+1}=C(n,2n)-C(n-1,2n)$

代码A(Luogu 1375)

#include<bits/stdc++.h>
#define mo 1000000007
using namespace std;
const int N=2e5+5;
long long ans;
int n;
long long ksm(long long x,long long y){
    long long ans=1;
    for(;y;y>>=1,x=x*x%mo){
        if(y&1){
            ans=ans*x%mo;
        }
    }
    return ans;
}
long long C(int n,int m){
    long long ans=1;
    for(int i=1;i<=m;i++,n--){
        ans=ans*n%mo*ksm(i,mo-2)%mo;
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    ans=C(2*n,n)-C(2*n,n-1);
    printf("%lld",(ans+mo)%mo);
}

代码B(Luogu 1722)

#include<bits/stdc++.h> 
using namespace std;
int h[110];
int main(){
    int n,i,j;
    h[0]=1;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        for(j=0;j<i;++j){
            h[i]=(h[i]+h[j]*h[i-1-j])%100;
        }
    }
    printf("%d\n",h[n]);
    return 0;
}

默慈金数

OEIS A001006

一个给定的数n的默慈金数是在一个圆上的n个点间，画出彼此不相交弦的全部方法的总数。

$M_{n+1}=M_n+\sum_{i=0}^{n-1}M_iM_{n-i-1}=\frac{(2n+3)M_n+3nM_{n-1}}{n+3}$

$M_n=\sum_{i=0}^{n/2}C(2i,n)cat(i)$

例子

1.在一个网格上，若限定每步只能向右移动一格，可以右上，右下，横向，向右，并禁止移动到y=0以下的地方，则以这种走法移动n步从(0,0)到(0,n)的可能形成的路径的总数为n的默慈金数。

2.有一个1*n的矩阵，固定第一个数为1，其他填正整数，且相邻数的差不能超过1，求方案数。

$ans[n]=3*ans[n-1]-M[n-2]$

代码

void get_motzkin(){
    long long x,y;
    m[1]=1,m[2]=2;
    for(int i=3;i<maxx;i++){
        exgcd(i+2,mod,x,y);
        x=(x%mod+mod)%mod;
        m[i]=(((2*i+1)*m[i-1])%mod+((3*i-3)*m[i-2])%mod)*x;
        m[i]=(m[i]%mod+mod)%mod;
    }
}

那罗延数

OEIS A001263

$N(n,k)=\frac{1}{n}C(n,k)C(n,k-1)$

• 那罗延三角中每一行的和为卡特兰数。即：$\sum_{a=1}^nN(n,a)=cat(n)$

例子
在由n对"("和")"组成的字符串中，共有k对"("与")"相邻，这样的字符串一共有N(n,k)个。

贝尔数

OEIS A000110

$B_{n+1}=\sum_{k=0}^nC(n,k)B_k$

$B_n=\sum_{k=1}^nS(n,k)\ (其中S(n,k)是第二类Stirling数)$

例子
划分一个集合的方案数。

代码

#include<bits/stdc++.h>
using namespace std;
long long S(long long m,long long n){//第二类Stirling数
    if(m==1||m==n){
        return 1;
    }
    else{
        return S(m-1,n-1)+S(m,n-1)*m;
    }
}  
int main(){  
    long long n,sum=0;
    n=read();
    for(long long i=1;i<=n;i++){
        sum+=S(i,n);
    }
    printf("%d",sum);
    return 0;  
}  

贝尔三角

OEIS A011971

伯努利数

OEIS A027641

递推式

$B_m=(m==0?1:0)-\sum_{k=0}^{m-1}C(m,k)\frac{B_k}{m-k+1}$

性质

$B_{2n+1}=0(当n\geq 1)$

例子

计算$\sum_{k=1}^{n}k^p$

• $\sum_{k=1}^{n}k^p=\frac{1}{p+1}\sum_{j=0}^{p}(-1)^jC(p+1,j)B_jn^{p+1-j}$
• $\sum_{k=1}^{n}k^p=\frac{1}{p+1}\sum_{k=1}^{p+1}C(k,p-1)B_{p+1-k}(n+1)^{k}$

(Zoj 2865，代码如下)

#include<bits/stdc++.h>
#define mod 1000000007
#define maxx 2018
using namespace std;
long long c[maxx][maxx];//组合数 
long long b[maxx];//伯努利数 
long long inv[maxx];//逆元 
long long tmp[maxx];
long long n;
inline long long read(){
    long long X=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
void init(){
    for(int i=0;i<maxx;i++){
        c[i][0]=c[i][i]=1;
        if(i==0){
            continue;
        }
        for(int j=1;j<i;j++){
            c[i][j]=(c[i-1][j]%mod+c[i-1][j-1]%mod)%mod;
        }
    }
    inv[1]=1;
    for(int i=2;i<maxx;i++){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    b[0]=1;
    for(int i=1;i<maxx;i++){
        long long ans=0;
        if(i==maxx-1){
            break;
        }
        for(int j=0;j<i;j++){
            ans+=c[i+1][j]*b[j];
            ans%=mod;
        }
        ans*=-inv[i+1];
        ans=(ans%mod+mod)%mod;
        b[i]=ans;
    }
}
long long work(int k){
    long long ans=inv[k+1],sum=0;
    for(int i=1;i<=k+1;i++){
        sum+=c[k+1][i]*tmp[i]%mod*b[k+1-i]%mod;
        sum%=mod;
    }
    ans*=sum;
    ans%=mod;
    return ans;
}
int main(){
    init();
    long long wxh=read();
    while(wxh--){
        n=read()%mod;
        int k=read();
        tmp[0]=1;
        for(int i=1;i<maxx;i++){
            tmp[i]=tmp[i-1]*(n+1)%mod;
        }
        printf("%lld\n", work(k));
    }
    return 0;
}

Burnside引理

不可用

Polya定理

不可用

五边形数

OEIS A000326

$f(n)=\frac{3^n-n}{2}$

定理

• 任何整数都可以表示为不超过5个五边形数的和。
• 但大多数的整数都可以表示不超过3个五边形数的和。(OEIS A003679(4x) OEIS A133929(5x))

广义五边形数

OEIS A001318

$f(n)=\frac{3^n\pm n}{2}$

五边形数定理

不可用

Farey序列&Stern-Brocot树

不可用

转载请表明出处,谢谢。