Luogu-4213-min25

题目链接

Luogu4213

思路

min25筛是用来处理积性函数的前缀和的一个方法，形如

$$\sum_{i=1}^n f(i)$$

cmxrynp这篇博客讲的很好。
这道题目我们需要处理出$\phi(i)与\mu(i)$的质数的前缀和权值即可，我们选择两个函数$g(i)表示质数前缀和,h(i)表示质数的个数前缀和$，然后我们就可以通过这两个函数找到

$$\begin{aligned} &\phi(i)=g(i)-h(i)\\ &\mu(i)=-h(i) \end{aligned}$$

例如$\phi(7)的前缀和=1+2+4+6=g(i)-h(i)=2+3+5+7-4$
$\mu(7)=-4$
这样就能套min25的板子了，因为mu的质数的高次幂全为0，所以我们可以不用枚举质数的幂，只需要枚举质数递归即可

代码实现

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
const int N = 1e5+10;
ll g[N<<1],h[N<<1],sn,sq,a[N<<1],n,sum[N<<1];
int prime[N],cnt,id;
inline ll Id(ll x){return x<=sn?x:id-n/x+1;}
ll SolvePhi(ll a,ll b)
{
	if(a<prime[b])return 0;
	//这一步处理质数部分，即S(a,b)之中的质数，a经过b轮筛之后剩下的质数的值，即为a的全部质数的权值减去加上的 
	//这里不能使用g，因为g已经被处理过了 
    ll ans = g[Id(a)]-sum[b-1]+(b-1);
    //这一步是合数部分 
    for(int i=b;i<=cnt&&prime[i]*prime[i]<=a;i++)//第一重循环枚举质数 
    {
    	ans+=(SolvePhi(a/prime[i],i+1)+prime[i])*(prime[i]-1);
    	for(ll x=prime[i]*prime[i],f=x-prime[i];x*prime[i]<=a;x*=prime[i],f*=prime[i])//第二重枚举指数 
    	ans+=(SolvePhi(a/x,i+1)+prime[i])*f;
	}
	return ans;
}
ll SolveMu(ll a,ll b)
{
   if(a<prime[b])return 0;
   ll ans = h[Id(a)]+(b-1);
   for(int i=b;i<=cnt&&prime[i]*prime[i]<=a;i++)//不需要枚举第二层，因为全为0
   {
   	ans-=SolveMu(a/prime[i],i+1);
   }
   return ans;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{ 
	scanf("%lld",&n);
	id=0;
	cnt=0;
	if(n==0)
	{
		puts("0 0");
		continue;
	}
	sn = sqrt(n);
	for(int i=1;i<=n;i=a[id]+1)a[++id]=n/(n/i),g[id]=((a[id]+1)*a[id])/2-1,h[id]=a[id]-1;
	//g[]表示处理完后质数的前缀和 
	//h[]表示处理完后质数的前缀质数个数
	//phi[]可以用g[i]-h[i]表示,如phi[7]的g为2+3+5+7-4(个数 
	//mu[]可以用-h[i]表示，如Mu[7]的质数的前缀和为-1-1-1-1(因为有四个质数 
	for(int i=2;i<=sn;i++)if(h[i]!=h[i-1])
	{
		prime[++cnt]=i;sum[cnt]=sum[cnt-1]+i;
		ll lim = 1ll*i*i;
		for(int j=id;a[j]>=lim;j--)
		{
			g[j]-=i*(g[Id(a[j]/i)]-g[i-1]);
			h[j]-=(h[Id(a[j]/i)]-h[i-1]); 
		}
	}
	for(int i=1;i<=id;i++)g[i]-=h[i],h[i]*=-1;
	printf("%lld %lld\n",SolvePhi(n,1)+1,SolveMu(n,1)+1);
    }
}