[模板] 积性函数 && 线性筛

左手的ㄟ右手 2022-01-08 00:43 227阅读 0赞

## 积性函数 ##

数论函数指的是定义在正整数集上的实或复函数.  
积性函数指的是当 \\((a,b)=1\\) 时, 满足 \\(f(a\*b)=f(a)\*f(b)\\) 的数论函数.  
完全积性函数指的是在任何情况下, 满足 \\(f(a\*b)=f(a)\*f(b)\\) 的数论函数.

### 常见的积性函数 ###

copy&modified from [积性函数 - 维基百科，自由的百科全书][-]

> φ(n) －欧拉函数  
> μ(n) －莫比乌斯函数，关于非平方数的质因子数目  
> gcd(n,k) －最大公因子，当k一定  
> d(n) －n的正因子数目  
> σ(n) －n的所有正因子之和  
> \\(σ\_k(n)\\) － 因子函数，n的所有正因子的k次幂之和，当中k可为任何复数。  
> \- k=0: \\(d(n)\\)  
> \- k=1: \\(\\sigma (n)\\)  
> I(n) －不变的函数，定义为 I(n) = 1 （完全积性）  
> Id(n) －单位函数，定义为 Id(n) = n（完全积性）  
> \\(Id\_k(n)\\) －幂函数，对于任何复数、实数k，定义为Idk(n) = n^k （完全积性）  
> \- k=0: \\(I(n)\\)  
> \- k=1: \\(Id(n)\\)  
> ε(n) －定义为：若n = 1，ε(n)=1；若 n > 1，ε(n)=0。别称为“对于狄利克雷卷积的乘法单位”（完全积性）  
> λ(n) －刘维尔函数，关于能整除n的质因子的数目  
> \\((\\frac np)\\) －勒让德符号，p是固定质数（完全积性）, 关于二次剩余

## 线性筛 ##

对于一个积性函数, 我们往往可以利用线性筛 \\(O(n)\\) 求出1-n的函数值.

线性筛只需求出一下几个值:

1.  \\(f(1)\\)
2.  \\(f(p)\\) when \\(p\\) is prime
3.  \\(f(p\*i)\\) when \\(p\\) is min prime factor && \\(p \\nmid i\\), then \\(f(p\*i) = f(p)\*f(i)\\)
4.  \\(f(p\*i)\\) when \\(p\\) is min prime factor && \\(p \\mid i\\)

前三个的求值是显然的;  
对于第四个, 大多数情况下, 这些函数都可以利用唯一分解得到表达式, 如\\(\\phi (n)\\),\\(\\mu (n)\\)等. 此时可以较容易求出第四个的递推式.

筛质数, \\(\\phi (n)\\),\\(\\mu (n)\\)的代码:

const int nsz=2e6+50;
    ll bnd=2e6;
    
    int nopr[nsz],pr[nsz],pp=0;
    ll mu[nsz],phi[nsz];
    void init(){
        nopr[1]=mu[1]=phi[1]=1;//a
        rep(i,2,bnd){
            if(nopr[i]==0)pr[++pp]=i,mu[i]=-1,phi[i]=i-1;//b
            rep(j,1,pp){
                if((ll)i*pr[j]>bnd)break;
                nopr[i*pr[j]]=1;
                if(i%pr[j])mu[i*pr[j]]=-mu[i],phi[i*pr[j]]=phi[i]*phi[pr[j]]; //c
                else{mu[i*pr[j]]=0,phi[i*pr[j]]=phi[i]*pr[j];break;} //d
            }
        }
    }

转载于:https://www.cnblogs.com/ubospica/p/10272514.html

[-]: https://zh.wikipedia.org/wiki/%E7%A9%8D%E6%80%A7%E5%87%BD%E6%95%B8