首页 > 其他分享 >杜教筛

杜教筛

时间:2023-07-09 14:12:12浏览次数:36  
标签:int ll long 杜教 vis unordered

 杜教筛起源于中学信息学队员杜瑜皓

它结合了三种算法,分别是:整除分块,狄利克雷卷积和线性筛

它主要是求解n较大时的积性函数的值

它的时间复杂度是O(n^(2/3)),小于O(n)

杜教筛在竞赛中很难出现

例题:P4213 【模板】杜教筛(Sum)

这是一道模板题,给出代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e6+39+7;
int prime[N],mu[N];ll phi[N];bool vis[N];
unordered_map<int,int>summu;
unordered_map<int,ll>sumphi;
void init(){
	int cnt=0;
	vis[0]=vis[1]=1;
	mu[1]=phi[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]){
			prime[cnt++]=i;
			mu[i]=-1;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt&&i*prime[j]<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]){
				mu[i*prime[j]]=-mu[i];
				phi[i*prime[j]]=phi[i]*phi[prime[j]];
			}else{
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
	for(int i=1;i<N;i++){
		mu[i]+=mu[i-1];
		phi[i]+=phi[i-1];
	}
}
int gsum(int x){return x;}
ll getsmu(int x){
	if(x<N)return mu[x];
	if(summu[x])return summu[x];
	ll ans=1;
	for(ll l=2,r;l<=x;l=r+1){
		r=x/(x/l);
		ans-=(gsum(r)-gsum(l-1))*getsmu(x/l);
	}
	return summu[x]=ans/gsum(1);
}
ll getsphi(int x){
	if(x<N)return phi[x];
	if(sumphi[x])return sumphi[x];
	ll ans=x*((ll)x+1)/2;
	for(ll l=2,r;l<=x;l=r+1){
		r=x/(x/l);
		ans-=(gsum(r)-gsum(l-1))*getsphi(x/l);
	}
	return sumphi[x]=ans/gsum(1);
}
int main(){
	init();int T;cin>>T;
	while(T--){
		int n;cin>>n;
		cout<<getsphi(n)<<' '<<getsmu(n)<<'\n';
	}
	return 0;
}

 

标签:int,ll,long,杜教,vis,unordered
From: https://www.cnblogs.com/zhanghx-blogs/p/17538679.html

相关文章

  • 杜教筛 & Min25 筛
    发现这个东西很容易忘,果然还是理解不够吧,写一篇博客方便以后复习。杜教筛目的是要求\(S(n)=\sum_{i=1}^nf(i)\)。我们需要构造两个函数\(g,h\)满足\(f*g=h\),其中\(h\)是一个积性函数且能快速求和。考虑求\(\sum_{i=1}^n\sum_{d|i}f(d)g(\dfrac{i}{d})=\sum_{i=1}......
  • 杜教筛 & Powerful Number 筛
    迪利克雷卷积对于数论函数\(F\),\(G\),我们定义迪利克雷卷积的结果\(H=F*G\)为\[H_n=\sum_{d\midn}F_dG_\frac{n}{d}\]有些好的性质,比如:对于积性函数\(F\)与\(G\),其迪利克雷卷积\(F*G\)也是积性函数;而在迪利克雷卷积的意义下,积性函数\(F\)的逆也是积性函数(逆满足\(F......
  • 【学习笔记】杜教筛
    如果我们要求一个积性函数\(f(x)\)的前缀和,可以用杜教筛在\(O(n^{\frac{2}{3}})\)的复杂度求出。具体地,构造函数\(g(x)\)和函数\(h(x)\),使得$h=f*g$,要求的式子是\(S(n)=\sum\limits_{i=1}^{n}f(i)\)。开始推式子。\[\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{......
  • 浅析数论--埃氏筛/欧拉筛/杜教筛
    \(\mathcal{0x01绪论}\)\(\mathcal{质数的判定试除法or六倍原理}\)一个合数的约数总是成对出现的,如果\(d|n\)(\(d\)能被\(n\)整除),那么\((n/d)|n\),因此我们判断一个......
  • [bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)
    题面设为的约数个数,给定,求题目分析有这样一个结论这道题就是下面这道题的数据增强版,那么这个结论的证明就不再赘述,请自行查看下面的(蒟蒻)博客​​传送门:[SDOI2015][bz......
  • [51Nod 1227] 平均最小公倍数 (杜教筛)
    题目描述求题目分析这道题其实是​​[51Nod1238]最小公倍数之和题解​​的简化版,或者说是本质…就直接上公式了令,则此处有一个常识证明如下当时,若,所以与互质的......
  • [51Nod 1237] 最大公约数之和 (杜教筛+莫比乌斯反演)
    题目描述求题目分析乍一看十分像裸莫比乌斯反演,然而的范围让人望而却步于是先变化一下式子枚举令k=Td则此时可以整除分块优化,每次算出相等的上下界后用莫比乌斯反演计......
  • [HDU 5608]Function(莫比乌斯反演 + 杜教筛)
    题目描述有求只有最多组数据题目分析如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的值令,根据莫比乌斯反演于是用筛出前项就行了......
  • 莫比乌斯反演与杜教筛
    莫比乌斯反演与杜教筛积性函数定义对于一个数论函数\(f\),若满足\(\forall(a,b)=1\)都有\(f(ab)=f(a)f(b)\),那么称\(f\)为积性函数。例子常见的积性函数有很多,......
  • 杜教筛
    杜教筛设现在要求积性函数\(f\)的前缀和,设\(\sum_{i=1}^{n}f(i)=S(n)\)找一个积性函数\(g\),考虑它们的狄利克雷卷积的前缀和\[\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^......