生之、如舟

2020-07-21 17:20 已编辑河南理工大学 golang

关注

数论模板

数论定理

最大公约数gcd

$gcd(a,b) = gcd(a,b-a)$
对于多个数求gcd有 $gcd(a,b,c) = gcd(a,b-a,c-b)$

素数个数估计函数

$\pi(x)$ 表示[0,x]中有多少个素数

$\pi(x)\approx\frac{x}{\ln (x)}$

切比雪夫定理

对于所有大于1的整数n，至少存在一个质数p，符合n < p < 2n

数学公式

海伦公式求三角形面积

$S = \sqrt(p*(p-a)*(p-b)*(p-c))$
公式中a，b，c分别为三角形三边长，p为半周长，S为三角形的面积。

求卡特兰数 (递推方式)

int N;
ll f[maxn];
f[0] = 1;f[1] = 1;
for(int i = 2;i<=N;i++){
    for(int j = 0;j<=i-1;j++){
        f[i] += f[j] * f[i-1-j];
    }
}

求卡特兰数 (公式方式 C(2n,n)/(n+1))

ll f[maxn];
f[0]=f[1]=1;
for(int i=2;i<=n;i++) f[i]+=f[i-1]*(4*i-2)/(i+1);

杂类公式

两个数x,y,若干个x和若干个y相加不能组合成的最大数是 $(x-1)*(y-1)-1$ ,也就是说 $(x-1)*(y-1)$ 及之后的数都可以用 $ax+by$ 来表示 $(a>=0,b>=0)$

欧拉函数

求某个数的欧拉函数值

ll euler(ll n){
    ll t=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            t-=t/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1) t-=t/n;
    return t;
}

欧拉函数值打表

const int maxn = 1e6+10;
int E[maxn];
void init()
{
    E[1] = 1;
    for(int i=2;i<maxn;i++){
        if(!E[i])
            for(int j=i;j<maxn;j+=i){
                if(!E[j]) E[j]=j;
                E[j] = E[j]/i*(i-1);
            }
    }
}

欧拉函数与质数一次性筛

int P[maxn],tail;//质数
bool vis[maxn];
int E[maxn]; //欧拉值
ll sum[maxn];//欧拉值前缀和
void initEP(int n)
{
    E[1] = 1;
    for (int i = 2; i <n; i ++ ){
        if (!vis[i]){
            P[tail ++ ] = i;
            E[i] = i-1;
        }
        for (int j = 0; P[j] * i <= n; j ++ ){
            vis[P[j] * i] = true;
            if (i % P[j] == 0){
                E[i * P[j]] = E[i] * P[j];
                break;
            }
            E[i * P[j]] = E[i] * (P[j] - 1);
        }
    }

    for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + E[i];
}

质数相关

判断一个数是否是质数

bool isprime(int a){
    if(a==1) return 0;
    if(a==2||a==3) return 1;
    if(a%6!=1 && a%6!=5) return 0;
    int temp=sqrt(a);
    for(int i=5;i<=temp;i+=6)
    {
        if(a%i==0||a%(i+2)==0) return 0;
    }
    return 1;
}

埃氏素数筛法

const int maxn = 1e6+10;
ll P[maxn],tail;
bool vis[maxn];

void init(){
    int len = (int)sqrt(maxn)+1;
    for(int i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;//将质数保存起来
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    } 
}

线性筛素数

bool vis[maxn];
int P[maxn/10],tail;

void initP(int N){
    for(int i = 2; i <=N; i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0; P[j] <= N / i; j++){
            vis[P[j] * i] = true;
            if(i % P[j] == 0) break;
        }
    }
}

质因数分解

P[]:质数表
ll div(ll x){
    for(int i = 0;i<tail && (ll)P[i]*P[i]<=x;i++){ //这里的P[i]*P[i]如果是int话会爆，所以强制转换一下
        if(x%P[i] == 0){
            int cnt = 0;
            while(x%P[i] == 0){
                cnt++;
                x/=P[i];
            }
        }
    }
}

求约数

对比较大的数求约数，在2e9范围内，一个数最多约数个数不超过1600，质因数不超过10个。
比普通的求约数快10倍

bool vis[maxn];
ll P[maxn],tail;
int yin[maxn],poww[maxn],cnt;
int yue[maxn],last;
void init(){
    for(ll i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}

ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}
void div(ll x){
    cnt = 0;
    for(int i = 0;i<tail && P[i]*P[i]<=x;i++){
        if(x%P[i] == 0){
            yin[cnt] = P[i];
            int coun = 0;
            while(x%P[i] == 0){
                coun++;
                x/=P[i];
            }
            poww[cnt++] = coun;
        }
    }
    if(x>1) yin[cnt] = x,poww[cnt++] = 1;
}
void DFS(int now,int num){ //当前枚举的位置，当前的约数值
    if(now >= cnt){
        yue[last++] = num;
    }else{
        int cur = num;
        for(int i = 0;i<=poww[now];i++){ //遍历0-最高次方
            DFS(now+1,cur);
            cur *= yin[now];
        }
    }
}

排列组合

计算 $C_{n}^{k}$

复杂度O(min(k,n-k))
公式 $\frac{a \times(a-1) \times \ldots \times(a-b+1)}{b !}$

ll C(ll n,ll K){
    if(K>n) return 0;
    if(K > n-K) K = n-K;
    ll m = 1,s = 1;//分母，分子
    for(int i = 0;i<K;i++){
        m = m*(n-i);
        s = s*(i+1);
    }
    return m/s;
}

预处理组合数 $C_{n}^{m} (0<=m<=n)$

ll C[N][N];
void initC(){ //初始化组合数C
    C[1][1] = 1;
    for(int i = 0;i<=N;i++) C[i][0] = 1;
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=i;j++){
            C[i][j] = C[i-1][j]+C[i-1][j-1];
        }
    }
}

预处理n固定不变的组合数 $C_{n}^{m}$

迭代公式为： $C_{n}^{k} = C_{n}^{k-1}\times (n-k+1)/k$

ll C[1000010];
void init(){
    ll ck = 1; C[0] = 1;
    for(ll k = 1;k<=n;k++){
        ck = ck*(n-k+1)/k;
        C[k] = ck;
    }
}

初始化所有的组合数在模mod的情况下的值

根据公式： $c(n,m)=n!/((n-m)!\times m!)$ 预处理出阶乘和阶乘的逆元,然后按公式进行计算

const ll maxn = 1e6+10;
const ll mod = 1000000007;
ll f[maxn],invf[maxn];
void init(int N){ 
    f[0]=invf[0]=f[1]=invf[1]=1;
    for(int i=2;i<=N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<=N;i++) invf[i]=invf[i-1]*invf[i]%mod;
}
ll C(ll n,ll m) 
{
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}

卢卡斯定理求大组合数

复杂度：logpN * (P + logP)
定理： $C_{a}^{b} \equiv C_{a\% p}^{b\%p} \times C_{a/p}^{b/p} (\mod p)$

ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%p;
        a = a*a%p;
        b>>=1;
    }
    return res;
}

ll C(ll n,ll K){
    if(K>n) return 0;
    if(K > n-K) K = n-K;
    ll m = 1,s = 1;
    for(int i = 0;i<K;i++){
        m = m*(n-i)%p;
        s = s*(i+1)%p;
    }
    return m*ksm(s,p-2)%p;
}

ll lucas(ll a,ll b){
    if(a<p && b<p) return C(a,b);
    else return C(a%p,b%p)*lucas(a/p,b/p)%p;
}

预处理阶乘和阶乘的逆元(取模)

ll jc[maxn],inv[maxn];//阶乘，阶乘的逆元
ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res * a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
void init(){
    jc[0] = 1;
    for(int i = 1;i<maxn;i++){
        jc[i] = jc[i-1] * i %mod;
        inv[i] = ksm(jc[i],mod-2);
    }
}

杂项

最大公约数与最小公倍数

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

逆元

线性求1～N关于质数P的逆元

ll N,P;
ll inv[maxn];
void init_inv(int N){
    inv[1] = 1;
    for(int i = 2;i<=N;i++){
        inv[i] = (P-P/i) * inv[P%i]%P;
    }
}

exgcd解线性同于方程

ax+by = c
d保存gcd(a,b)的结果，x,y是c = gcd(a,b)时对应的解
x，y的解系： $\left\{\begin{array}{l} x=\frac{c}{d} x+\frac{a}{d} \\ y=\frac{c}{d} y-\frac{b}{d} \end{array}\right.$
方程右边的x,y是c = gcd(a,b)时对应的解

void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a, x = 1, y = 0;
        return;
    }
    ex_gcd(b, a % b, d, y, x);
    y -= x * (a / b);
}

EXGCD求逆元

ax+by = 1 (mod P) 只要a与p互质就可以求出，a关于p的逆元

void exgcd(int a,int b,int& d,int& x,int& y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}

int inv(int a, int p)
{
    int d, x, y;
    exgcd(a, p, d, x, y);
    return d == 1 ? (x+p)%p : -1;
}

费马小定理求逆元(快速幂求逆元)

费马小定理： $a^{P-1} = 1 (\mod P)$ （P是质数，且a和P互质）

ll ksm(ll a ,ll b,ll P){
    ll res = 1;
    while(b){
        if(b&1) res = (res*a)%P;
        a = a*a%P;
        b>>=1;
    }
    return res;
}
ksm(a,P-2,P): 求a关于p的逆元

Ryuichi的算法分享文章被收录于专栏

分享我的一些算法题解，致力于把题解做好，部分题解可能会采用视频的形式来讲解。