[总结] 线性筛与积性函数

[总结] 线性筛与积性函数

利用线性筛中一个数仅仅被它最小的质因子筛掉的性质,结合积性函数的特殊性质,往往可以预处理出积性函数的值。

\(\varphi(x)\)

设 \(P\) 是质数,显然 \(\varphi(p)=p-1\)。

根据定义式:\(\varphi(x)=x\cdot \prod_{i=1}^k{\frac{p_i-1}{p_i}}\),则 \(\varphi(p^k)=p^{k-1}\varphi(p)=p^{k-1}(p-1)\)

由于是积性函数,所以当 \(i\) 与 \(p\) 互质时,\(\varphi(i\cdot p)=\varphi(i)\varphi(p)\)。

我们只需要考虑 \(i\) 与 \(p\) 不互质的情况,即 \(i\ mod\ p=0\) 时。

不妨构造出互质的式子:

\(\varphi(p\cdot i)=\varphi(p^k\cdot\frac{i}{p^{k-1}})=\varphi(p^k)\varphi(\frac{i}{p^{k-1}})=p^{k-1}(p-1) \varphi(\frac{i}{p^{k-1}})\)

\(\varphi(i)=\varphi(p^{k-1}\cdot \frac{i}{p^{k-1}})=p^{k-2}(p-1)\varphi(\frac{i}{p^{k-1}})\)

发现当 \(i\) 的最小质因子 \(p\) 的次数为 \(k-1\) 时,\(\varphi(p\cdot i)=p\cdot \varphi(i)\)

int primes[maxn],cnt=0,phi[maxn];
bool notp[maxn];
void make_phi(int n){
	notp[1]=true;
	for(int i=2;i<=n;i++){
		if(!notp[i])primes[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt;j++){
			int tmp=primes[j]*i;if(tmp>n)break;
			notp[tmp]=true;
			if(i%primes[j])phi[tmp]=phi[i]*phi[primes[j]];
			else{
				phi[tmp]=phi[i]*primes[j];break;
			}
		}
	}
    return ;
}

\(\sigma_k(x)\)

\(\sigma_k(x)=\sum_{d|x}d^k\)

\(\sigma_0(x)\),意义为约数的个数。

证明过程类似于上面,直接给出 \(i \ mod \ p=0\) 时的结论:

\(\sigma_0(i\cdot p)=\sigma_0(i)\cdot\frac{d+2}{d+1}\)

其中 \(d=k-1\),也就是 \(i\) 的最小质因子 \(p\) 的次幂。

这其实在我做过的题当中是有应用的,我当时还在感慨题解怎么这么胡

CF920F SUM and REPLACE

这是当时筛法的代码,也是核心代码:

void init(){
	d[1]=1;g[1]=1;
	for(int i=2;i<=maxm-5;i++){
		if(!notp[i])primes[++cnt]=i,g[i]=1,d[i]=2;
		for(int j=1;j<=cnt;j++){
			LL k=i*primes[j];
			if(k>maxm-5)break;
			if(i%primes[j]==0){
				notp[k]=true;
				g[k]=g[i]+1;
				d[k]=1LL*d[i]*(g[i]+2)/(g[i]+1);
				break;
			}
			else{
				notp[k]=true;
				g[k]=1;
				d[k]=d[i]*d[primes[j]];
			}
		}
	}
    return ;
}

\(\sigma_1(x)\),意义为 \(x\) 的所有因子的和。

定义式为:

\(\sigma_1(x)=\prod_{p|x}\sum_{i=0}^{c_i}p^i\)

直接给出 \(i\ mod\ p=0\) 时的式子。

\(\sigma_1(p\cdot i)=\frac{\sigma_1(i)}{\sigma_1(p^{k-1)}}\cdot \sigma_1(p^k)\)

其实就是按照思路展开定义求解,因为没有好用的化简来处理。

可以预处理快速幂,然后 \(\text O(1)\) 查询。

贴一张 \(gyx\) 学长的 pdf 截图:

[总结] 线性筛与积性函数

上一篇:【自适应辛普森】积分计算


下一篇:[模板] FFT 快速傅里叶变换