[LOJ6053]简单的函数：Min

分析

因为题目中所给函数\(f(x)\)的前缀和无法较快得出，考虑打表以下两个函数：

\[g(x)=x \times [x是质数]
\]

\[h(x)=1 \times [x是质数]
\]

这两个函数的前缀和都可以通过Min_25筛第一阶段的处理得出，时间复杂度为\(O(\frac{n^{\frac{3}{4}}}{\log n})\)。

我们发现：

\[f(2)=g(2)+h(2)
\]

\[f(x)=g(x)-h(x),x是质数且 x \neq 2
\]

然后就可以把这两个函数一起做Min_25筛的第二阶段，\(y=1\)的时候特判一下加个\(2\)就好了，时间复杂度为\(O(\frac{n^{\frac{3}{4}}}{\log n})\)。（太鶸了并不会证时间复杂度）

（还是写哈希表更直观，虽然也更慢）

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline LL read(){

	LL x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const LL MAXN=1e10+5;

const int MOD=1e9+7;

const int INV2=5e8+4;

const int HASH=3e6-1;

const int MAXR=2e5+5;

LL n,num[MAXR];

int prm[MAXR],sum[MAXR],cnt;

int g0[MAXR],g1[MAXR],tot;

int id1[MAXR],id2[MAXR];

bool vis[MAXR];

void pre_process(int n){

	rin(i,2,n){

		if(!vis[i]) prm[++cnt]=i,sum[cnt]=(sum[cnt-1]+prm[cnt])%MOD;

		rin(j,1,cnt){

			if(i*prm[j]>n) break;

			vis[i*prm[j]]=true;

			if(i%prm[j]==0) break;

		}

	}

}

inline int getid(LL x){

	if(x<=MAXR-5) return id1[x];

	else return id2[n/x];

}

inline int min_25(LL x,int y){

	if(x<2||x<prm[y]) return 0;

	int xx=getid(x),ret=(((g1[xx]-sum[y-1])-(g0[xx]-(y-1)))%MOD+MOD)%MOD;

	if(y==1) ret=(ret+2)%MOD;

	rin(i,y,cnt){

		if(1ll*prm[i]*prm[i]>x) break;

		register LL now=prm[i];

		for(register int j=1;now*prm[i]<=x;++j,now*=prm[i])

			ret=(ret+1ll*(prm[i]^j)*min_25(x/now,i+1)+(prm[i]^(j+1)))%MOD;

	}

	return ret;

}

int main(){

	n=read();pre_process((int)(sqrt(n)+0.5));

	for(register LL i=1,nxti=0;i<=n;i=nxti+1){

		num[++tot]=n/i,nxti=n/num[tot];

		if(num[tot]<=MAXR-5) id1[num[tot]]=tot;

		else id2[n/num[tot]]=tot;

		g0[tot]=(num[tot]-1)%MOD;

		g1[tot]=(2+num[tot])%MOD*((num[tot]-1)%MOD)%MOD*INV2%MOD;

	}

	rin(i,1,cnt){

		rin(j,1,tot){// num[j] from big to small.

			if(1ll*prm[i]*prm[i]>num[j]) break;

			int k=getid(num[j]/prm[i]);

			g0[j]=(g0[j]-(g0[k]-(i-1))+MOD)%MOD;

			g1[j]=((g1[j]-1ll*prm[i]*(g1[k]-sum[i-1]))%MOD+MOD)%MOD;

		}

	}

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

	return 0;

}

巴特西

[LOJ6053]简单的函数：Min_25筛

分析

代码

最新文章

热门文章