数论寄础

hubingshan · 2022-07-30 14:41:47 · 个人记录

负一、学习链接

莫反基础
素数

零、前置知识

二项式定理：\sum\limits_{i=0}^nC_k^i\times a^i\times b^{n-i}=(a+b)^k

常见用法：\sum\limits_{i=0}^nC_k^i\times -1^i=(1+(-1))^k

约数函数性质: d(i\times j)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]

高维情况: d(ABC) = \sum\limits_{x|A} \sum\limits_{y|B} \sum\limits_{z|C} [\gcd (x,y) = 1] [\gcd (y,z) = 1] [\gcd (x,z) =1]

一、亿些定义

积性函数：\forall a\perp b , f(ab)=f(a)f(b)

完全积性函数：\forall a,b,f(ab)=f(a)f(b)

性质：若 f,g 均为积性函数，则f* g 也是积性函数

例子：

• 单位函数：e(n)=[n=1]

• 恒等函数：id(n)=n,id_k(n)=n^k

• 常数函数：I(n)=1

• 欧拉函数：\varphi(n)=\sum\limits_{i=1}^n[gcd(i,n)=1]

  二、整除分块

可参考整除分块向上以及向下取整

适用情况：\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor

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

单个参数：

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

两个参数情况：

for(int l=1,r;l<=n;l=r+1)
{
    r=min(n/(n/l),m/(m/l));
    ans+=(r-l+1)*val(n/l,m/l);
}

三、迪利克雷卷积(Dirichlet)

数论函数 f,g 的迪利克雷卷积定义为：

记为 h=f* g

性质：满足交换律、结合律、分配律

定理：若 f,g 均为积性函数，则f* g 也是积性函数

四、莫比乌斯反演

前置知识：

莫比乌斯函数:

当 n=1 时，\mu(n)= 1

当 n 含有平方因子时，\mu(n)= 0

当 n 有 k 个不同的质因子时，\mu(n)= (-1)^k

定理1：\mu* I=e 即 \sum\limits_{d|n}\mu(d)=[n=1]

证明： n=1 时显然，n>1时，产生贡献的因子都可以互相抵消
严谨证明： 设 n=\prod\limits_{i=1}^kp_i^{c_i},n'=\prod\limits_{i=1}^kp_i
则\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)=\sum\limits_{i=0}^kC_k^i*(-1)^i=(1+(-1))^k
得证。

定理2：f* I=g\Leftrightarrow f=g*\mu

证明：两边同时卷上 \mu

五、欧拉函数

定理：\varphi* I=id

证明：\varphi(n)=\sum\limits_{i=1}^n[gcd(i,n)=1]=\sum\limits_{i=1}^n\sum\limits_{d|i,d|n}\mu(d)=\sum\limits_{d|n}\mu(d)\sum\limits_{i=1}^n[d|i]=\sum\limits_{d|n}\mu(d)\frac{n}{d}=\mu* id

所以\varphi=\mu*id
故 \varphi* I=id

常用变形：\gcd(i,j)=\sum\limits_{d|\gcd(i,j)}\varphi(d)\times I(\frac{n}{d})=\sum\limits_{d|i}\sum\limits_{d|j}\varphi(d)

六、O(n)筛法

void pre(){
    vis[1]=g[1]=f[1]=mu[1]=phi[1]=d[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            pri[++tot]=i;//质数 
            phi[i]=i-1;//欧拉函数 
            mu[i]=-1;//莫比乌斯 
            d[i]=2;//约数个数 
            num[i]=1;//最小质因子个数 
            f[i]=i+1;//约数和 
            g[i]=i+1;//最小质因子的等比数列 
        } 
        for(int j=1;j<=tot;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                mu[i*pri[j]]=0;
                num[i*pri[j]]=num[i]+1;
                d[i*pri[j]]=d[i]/num[i*pri[j]]*(num[i*pri[j]]+1);
                g[i*pri[j]]=g[i]*pri[j]+1;
                f[i*pri[j]]=f[i]/g[i]*g[i*pri[j]];
                break;
            }
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
            mu[i*pri[j]]=-mu[i];
            d[i*pri[j]]=d[i]*2;
            num[i*pri[j]]=1;
            f[i*pri[j]]=f[i]*f[pri[j]];
            g[i*pri[j]]=pri[j]+1;
        }
    }
}

推柿子时尽量往整除分块或者能预处理的函数方向推

七、杜教筛

要求S(n)=\sum\limits_{i=1}^nf(i)
构造积性函数 h,g，使得 h=f*g。
有：$ \sum\limits{i=1}^{n}h(i)=\sum\limits{i=1}^{n}\sum\limits{d|i}f(\frac{i}{d})g(d)\ =\sum\limits{d=1}^{n}g(d)\sum\limits{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)\ =\sum\limits{d=1}^{n}g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)

S(n)=\frac{\sum\limits{i=1}^{n}h(i)-\sum\limits{d=2}^{n}g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)}{g(1)}