min25筛学习笔记

目录

• min25筛学习笔记
  • part0
  • part1
  • part2
  • code
  • 用法
    • 筛 $mu$
    • 筛 $phi$
  • ZROI1838

min25筛学习笔记

min25筛用于求

[sum_{i=1}^n f(i) ]

其中 (f) 是一个积性函数且能快速求 (f(p^e)) 。除此之外我们还要找到一个完全积性函数 (f') 可以快速求前缀和且 (f(p)=f'(p)) 。

part0

先线性筛出 (le sqrt(n)) 的质数，设 (p) 代表质数， (p_j) 是第 (j) 个质数。

part1

首先需要求出一个dp数组：

[g(n,j) = sum_{iin p}^n f'(i)+sum_{i ot in p}^n [ ext{minp}_i>p_j]f'(i) ]

即质数和最小质因子大于(p_j)的合数处的 (f'_i) 之和。

考虑递推，从 (j-1) 转移到 (j) 时减去了最小质因子为 (p_j) 的合数的 (f_i')，由于 (f’) 是完全积性函数，我们可以提出一个 (f'(p_j)) ，则

[g(n,j)=g(n,j-1)-f'(p_j)left(gleft(frac{n}{p_j},{j-1} ight)-gleft(p_{j-1},j-1 ight) ight) ]

然后 (frac{n}{x}) 只有(sqrt n) 种，可以离散化，(gleft(p_{j-1},j-1 ight))就预处理一下质数的 (f_p') 前缀和。

part2

接着计算答案，我们考虑把质数和合数的答案分开，设 (S(n,j)) 表示最小质因子大于 (p_j) 处的 (f_i) 之和，那么

[S(n,j)=g(n, ext{maxj})-g(p_{j},j)+sum_{k>j,e,p_k^e<n}f(p_k^e)left(Sleft(frac{n}{p_k^e},k ight)+[e ot=1] ight) ]

其中 ( ext{maxj}) 是 (g) 中 (j) 的最大取值，也即最大的使 (p_jle sqrt(n)) 的 (j)

前面是质数的情况，(g(n, ext{maxj}))是所有质数的情况，因为最小质因子 $>sqrt n $ 的合数并不存在。还要减去(le p_j) 的质数的情况。

后面是合数的情况，枚举最小质因子和次数，然后利用积性函数的性质递归。

边界是(nle p_j)，此时(S(n,j)=0)。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+1;
#define FOR(i,a,b) for(int i=a;i<=b;++i)
const int mod = 1e9+7,iv2=500000004,iv3=333333336;
ll n,s1[N],s2[N],isp[N],pri[N],top;
ll s;
void init(int len){
	FOR(i,2,len){
		if(!isp[i]){
			pri[++top]=i;
			s1[top]=(s1[top-1]+i)%mod;
			s2[top]=(s2[top-1]+1ll*i*i)%mod;
		}
		for(int j=1;j<=top&&i*pri[j]<=len;j++){
			isp[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
int pos1[N],pos2[N];
ll g1[N],g2[N],tot,val[N];
ll S(ll x,ll y){
	if(pri[y]>=x) return 0;
	int k=(x<=s)?pos1[x]:pos2[n/x];
	ll res=(2ll*mod-g1[k]+g2[k]+s1[y]-s2[y])%mod;
	for(int i=y+1;pri[i]*pri[i]<=x&&i<=top;i++){
		for(ll j=pri[i],tms=1;j<=x;j*=pri[i],tms++){
			ll wn=j%mod;
			res=(res+wn*(wn-1)%mod*(S(x/j,i)+(tms!=1))%mod)%mod;
		}
	}
	return res;
}
int main(){
	scanf("%lld",&n);
	s=sqrt(n);
	init(s);
	for(ll l=1,r=0;l<=n;l=r+1){
		//printf("%lld %lld
",l,r);
		r=min(n,n/(n/l));
		ll w=n/l,wn=w%mod;
		val[++tot]=w;
		g1[tot]=(1ll*wn*(wn+1)%mod*iv2%mod+mod-1)%mod;
		g2[tot]=((1ll*wn*(wn+1)%mod*iv2%mod*((2ll*wn+1)%mod)%mod*iv3%mod)+mod-1)%mod;
		if(w<=s) pos1[w]=tot;
		else pos2[n/w]=tot;
	}
	FOR(i,1,top){
		for(int j=1;j<=tot&&pri[i]*pri[i]<=val[j];j++){
			int nexp;if(val[j]/pri[i]<=s) nexp=pos1[val[j]/pri[i]];else nexp=pos2[n/(val[j]/pri[i])];
			g1[j]=(g1[j]-pri[i]*((g1[nexp]-s1[i-1]+mod)%mod)%mod+mod)%mod;
			g2[j]=(g2[j]-pri[i]*pri[i]%mod*((g2[nexp]-s2[i-1]+mod)%mod)%mod+mod)%mod;
		}
	}
	printf("%lld
",(S(n,0)+1)%mod);
	return 0;
}

用法

筛 (mu)

(mu(p^e)=(-1)^e)，(f'=-1)

筛 (phi)

(phi(p^e)=(p-1)p^{e-1},f'= ext{id}-1)

ZROI1838

题意：求

[sum_{1 leq a_{1}, a_{2}, cdots, a k leq n}leftlfloor frac{n}{operatorname{lcm}left(a_{1}, a_{2}, cdots, a_{k} ight)} ight floor ]

推导：

[=sum_{1 leq a_{1}, a_{2}, cdots, a k leq n}sum_{a_1|j,a_2|j,cdots,a_k|j}^n1 \=sum_{j=1}^nsum_{a_1|j,a_2|j,cdots,a_k|j}^n1 \=sum_{j=1}^n d(j)^k ]

于是使用min25筛，(d(p^e)^k=(e+1)^k)，(f'=2^k)（常数）。