$Min\_25$筛学习笔记

时间：2022-08-26 21:06:19

\(Min\_25\)筛学习笔记

这种神仙东西不写点东西一下就忘了QAQ

资料和代码出处

资料2

资料3

打死我也不承认参考了yyb的

\(Min\_25\)筛可以干嘛？下文中未特殊说明\(P\)均指质数集合,\(p_i\)或\(p\)指某个具体质数。

求一类积性函数\(f(x)\)的前缀和，需要满足\(f(p)\)可以写成多项式的形式，或者操作一下可以写成多项式（如例题），且\(f(p^k)\)能快速求出。

讲真学这个东西比我什么都不会的时候学\(FFT\)都累。

Round 1

先求质数的贡献。我们要求

\[\sum_{i=1}^x[i是质数]f(i)$$。

我们可以设

$$g(n,j)=\sum_{i=1}^{n}[i \in P \ or\ \min(p)>P_j]f(i)\]

注意到当\(p_j^2>x\)时，\(g(n,j)=g(n,j-1)\)因为没有新的贡献了，所以我们只要筛到\(\sqrt n\)的质数就可以了，这也是降低复杂度的关键。

我们还注意到\(g(n,|P|)=\sum_{i=1}^x[i是质数]f(i)\)，\(|P|\)是\(\sqrt n\)内的质数集合大小。

关于\(g(n,j)\)的转移，我们有：

\[g(n,j)=g(n,j-1)-f(P_j)[g(\frac{n}{P_j},j-1)-\sum_{i=1}^{j-1}f(P_i)],P_j^2\le n
\]

意思大概就是减掉所有最小质因子为\(p_j\)的贡献，但由于\(g(\frac n{p_j},j-1)\)里包含了质数，而\(<p_j\)的质数是不能算的，所以要减掉。

由于我们只需要\(g(n,|P|)\)，所以下面的代码是一维的，用递推实现。注意到过程中我们只需要\(g(\lfloor\frac ni\rfloor,|P|)\)，所以最多只有\(2\sqrt n\)种取值

至于实现，由于我参考了\(gsy\)的实现，痛不欲生，于是决定把他的代码蒯走。这份代码是筛\(f(p)=1\)的。

//这两个鬼id就是你在杜教筛中碰到的卡常卡空间技巧，这份代码你理解了这个就能看懂

//至于YL，是机房众人mo的巨佬，所以是模数

//Sq是根号n

for (int i=1,j;i<=n;i=j+1)

{

    j=n/(n/i);w[++m]=n/i;g[m]=(w[m]-1)%YL;//除法分块，根号n求出所有有用的值

    if(w[m]<=sq)id1[w[m]]=m;else id2[n/w[m]]=m;

}

for (int j=1;j<=tot;++j)

    for (int i=1;i<=m&&pri[j]*pri[j]<=w[i];++i)//i再往上就是所有的质数，会被后面抵消

    {

        int k=(w[i]/pri[j]<=sq)?id1[w[i]/pri[j]]:id2[n/(w[i]/pri[j])];

        g[i]=(g[i]-g[k]+(j-1))%YL;g[i]=(g[i]+YL)%YL;

    }

Round 2

然而敌人并没有这么容易就被打倒，我们还有合数没算呢。那么我们鼓捣一个\(S(n,i)\)出来

\[S(n,j)=\sum_{i=1}^n[\min(p)\ge P_j]f(i)
\]

注意\(S(n,1)\)没算到\(f(1)\)。答案就是\(S(n,1)+f(1)\)。

递推式来了

\[S(n,j)=(质数的贡献)+(合数的贡献)
\]

有没有感觉被骗了\(QwQ\)，我们继续

\[(质数的贡献)=g(n,|P|)-\sum_{i=1}^{j-1}f(P_i)
\]

\[(合数的贡献)=\sum_{k=j}^{P_k^2\le n}\sum_{e=1}^{P_k^{e+1}\le n}S(\frac{n}{P_k^e},k+1)\times f(P_k^e)+f(P_k^{e+1})
\]

经过\(YL\)的指点，我可以口胡一下了，每个合数要在最小质因子处被筛到。当\(\frac n{p_k^e}<p_{k+1}\)时，肯定是\(0\)就没必要继续了。

举个栗子，形如\(t*p_k^3\)（其中\(t\)的最小质因子大于\(p_k\)）的数会被\(S(\frac n{p_k^3},4)\)包含。

由于\(S\)这个函数在任何时候都不包含\(f(1)\)所以我们要手动加上\(f(p_k^2),f(p_k^3),...,f(p_k^{e+1})\)其中\(p_k^{e+2}>n\)。什么，你问我\(f(p_k)\)去哪了，这不是个质数么。

完结撒花

放上LOJ6053简单的函数作为例题，这里面的\(p\)^\(c\)对于质数来说除了\(2\)以外都是\(p-1\)，像个多项式。

代码中\(g(x,|P|)=\sum_{i=1}^x[i是质数]i\)，\(h(x,|P|)=\sum_{i=1}^x[i是质数]1\)

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

inline ll in()

{

	ll k=0;char ch=gt;

	while(ch<'-')ch=gt;

	while(ch>'-')k=k*10+ch-'0',ch=gt;

	return k;

}

const int N=1e6+5,YL=1e9+7,mod=YL;

inline int MO(const int &x){return x>=YL?x-YL:x;}

ll n,w[N];

int np[N],pr[N],tot,h[N],g[N],sp[N],id1[N],id2[N],m,sq;

void seive(int n)

{

	for(int i=2;i<=n;++i)

	{

		if(!np[i])pr[++tot]=i,sp[tot]=MO(sp[tot-1]+i);

		for(int j=1;i*pr[j]<=n;++j)

		{np[i*pr[j]]=1;if(i%pr[j]==0)break;}

	}

}

int S(ll x,int y)

{

	if(x<=1||pr[y]>x)return 0;

	int k=(x<=sq?id1[x]:id2[n/x]);

	int res=MO(((ll)g[k]-h[k]-sp[y-1]+y-1)%YL+YL);

	if(y==1)res+=2;

	for(int i=y;i<=tot&&1ll*pr[i]*pr[i]<=x;++i)

	{

		ll p1=pr[i],p2=p1*pr[i];

		for(int e=1;p2<=x;++e,p1=p2,p2*=pr[i])

			res=MO(res+(1ll*S(x/p1,i+1)*(pr[i]^e)+(pr[i]^e+1))%YL);

	}

	return res;

}

int main()

{

	n=in();sq=sqrt(n);seive(sq);ll t;

	for(ll i=1,j;i<=n;i=j+1)

	{

		j=n/(n/i),w[++m]=n/i;

		if(w[m]<=sq)id1[w[m]]=m;else id2[n/w[m]]=m;

		h[m]=(w[m]-1)%YL;g[m]=((w[m]+2)%YL)*((w[m]-1)%YL)%YL;

		if(g[m]&1)g[m]+=YL;g[m]>>=1;

	}

	for(int j=1;j<=tot;++j)

		for(int i=1;i<=m&&1ll*pr[j]*pr[j]<=w[i];++i)

		{

			t=w[i]/pr[j];int k=(t<=sq?id1[t]:id2[n/t]);

			h[i]=MO((h[i]-h[k]+j-1)%YL+YL);

			g[i]=MO(MO(g[i]-1ll*pr[j]*(g[k]-sp[j-1])%YL)+YL);

		}

	printf("%d\n",S(n,1)+1);

	return 0;

}

一些也许是高阶的应用？

筛与最小质因子有关的东西，用第一步筛，筛的时候顺便处理一下。

筛最大次大质因子有关，考虑后面的筛，其中在乱搞一下就行了。

主要要深刻的理解min_25筛的过程，本质上是容斥？（我口胡的

多做题就明白了。

我偷偷的把YCB的题单蒯过来。

泥萌看着办吧。

随机推荐

  1. OpenCASCADE Hidden Line Removal

    OpenCASCADE Hidden Line Removal eryar@163.com Abstract. To provide the precision required in industr ...

  2. ATT 解锁手机

    最近豪们都在忙着买买买950 本土鳖左瞅瞅右看看实在钱包不够豪 正好看到美帝640打折39刀 (http://www.microsoftstore.com/store/msusa/en_US/pdp/ ...

  3. 使用 Python 抓取欧洲足球联赛数据

    Web Scraping在大数据时代,一切都要用数据来说话,大数据处理的过程一般需要经过以下的几个步骤    数据的采集和获取    数据的清洗,抽取,变形和装载    数据的分析,探索和预测    ...

  4. Aop 是面向切面编程&comma;

    Aop 是面向切面编程,是在业务代码中可以织入其他公共代码(性能监控等),现在用普通的方法实现AOP http://blog.csdn.net/heyanfeng22/article/details/ ...

  5. Redis适用于高并发的递增、递减功能

    递增指令:incr(默认从0开始) 递减指令:decr(默认从0开始,递减会出现负数,这点跟memcache不一样,mc到0) 如下: 附上shardedJedisPool和JedisCluster的 ...

  6. ubuntukylin提取root权限及mongoDB部署

    UbuntuKylin下安装Mongodb (参照UbuntuKylin下安装Mongodb一文安装成功后的心得) 1.官网下载安装包  http://www.mongodb.org/dr/fastd ...

  7. Centos 6&period;5 安装 chrome &comma; mplayer &comma; alarm &comma; clock

    http://my.oschina.net/jianweizhang/blog/306946 Chrome wget http://chrome.richardlloyd.org.uk/install ...

  8. jquery放大镜插件与样式

    这是放大镜插件链接,我已经上传到我博客http://files.cnblogs.com/valiant1882331/%E6%94%BE%E5%A4%A7%E9%95%9C%E6%8F%92%E4%B ...

  9. 【POJ 3669 Meteor Shower】简单BFS

    流星雨撞击地球(平面直角坐标第一象限),问到达安全地带的最少时间. 对于每颗流星雨i,在ti时刻撞击(xi,yi)点,同时导致(xi,yi)和上下左右相邻的点在ti以后的时刻(包括t)不能再经过(被封 ...

  10. android Listview，gridview局部刷新，部分刷新

    众所周知Listview和Gridview的刷新界面的方式是调用adapter.notifyDataSetChanged()进行界面刷新. 但是此方法有其弊端,他是将界面中的数据全部刷新一遍,不论数据 ...

相关文章