【UOJ#188】Sanrd（min_25筛）

题面

UOJ

题解

今天菊开讲的题目。(千古神犇陈菊开，扑通扑通跪下来)

题目要求的就是所有数的次大质因子的和。

这个部分和\(min\_25\)筛中枚举最小值因子有异曲同工之妙。

min_25筛什么的戳这里

并且这题并没有积性函数。

所以我们先筛出质数个数。

然后考虑如何计算答案\(S(n,1)\)

首先看初值，假设当前计算的是\(S(x,y)\)

表示的是\([1,x]\)中，所有最小质因子大于等于\(Prime_y\)的贡献

所有质数的贡献显然是\(0\)，我们考虑计算合数的答案。

枚举最小质因子以及这个质因子的次幂，在只剩下两个质因子的时候统计答案。

既然只剩下两个质因子，那么需要计算的就是\(x\)中所有大于等于\(Prime_y\)的质数。

因为\(S(x,y)\)一定右\(S(?,y-1)\)转移过来

那么它的次小质因子就是\(Prime_{y-1}\)，直接计算即可。

还需要额外考虑\(p^k\)的贡献就是\(p\)

#include<iostream>

#include<cmath>

using namespace std;

#define ll long long

#define MAX 1000000

ll L,R,ans,w[MAX],g[MAX],Sqr;

int id1[MAX],id2[MAX],m,pri[MAX],tot;

bool zs[MAX];

void pre(int n)

{

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

	{

		if(!zs[i])pri[++tot]=i;

		for(int j=1;j<=tot&&i*pri[j]<=n;++j)

		{

			zs[i*pri[j]]=true;

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

		}

	}

}

ll S(ll n,ll x,int y)

{

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

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

	ll ret=1ll*pri[y-1]*(g[k]-y+1);

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

	{

		ll p1=pri[i],p2=1ll*pri[i]*pri[i];

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

			ret+=S(n,x/p1,i+1)+pri[i];

	}

	return ret;

}

ll Solve(ll n)

{

	tot=m=0;pre(Sqr=sqrt(n));

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

	{

		j=n/(n/i);w[++m]=n/i;g[m]=w[m]-1;

		if(w[m]<=Sqr)id1[w[m]]=m;

		else id2[j]=m;

	}

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

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

		{

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

			g[i]-=g[k]-j+1;

		}

	return S(n,n,1);

}

int main()

{

	cin>>L>>R;

	cout<<Solve(R)-Solve(L-1)<<endl;

	return 0;

}