powerful number 小记

想学 powerful number 请直接去阅读 zzq 的博客，这篇只是用来水。

---

简介

利用 Powerful Number 可以求部分积性函数 (F(x)) 的前缀和。

我们可以构造一个积性函数 (G(x))，使得 (x) 为质数时 (G(x)=F(x))，并且 (G(x)) 的前缀和可以快速计算。

设有积性函数 (H(x)) 使得 (F=G * H)，即 (H=F/G)。则有

[sum_{i=1}^n F(i)=sum_{ij leq n} H(i)G(j)=sum_{i=1}^n H(i) sum_{j=1}^{n/i} G(j) ]

可以发现，(x) 为质数时 (H(x)=0)，由此可以得到 (H(x) eq 0) 的位置，(x) 所有质因子的次数一定 (ge 2)，我们将这样的数称为 powerful number。

可以这样的数不超过 (sqrt n) 个，故可以直接爆搜这样的数。

求 (H(p^e)) 的点值可以安排类似多项式求逆的东西，(F(p^e),G(p^e)) 的点值通常可以 (O(1)/O(e)) 得到。

模板/代码

void dfs(int u, ll x, ll w)
{
	if(!w) return ;
	ans+=w*sumG(n/x);
	for(int i=u;i<=tot&&x<=n/pri[i]/pri[i];++i)
	{
		if(h[i].size()==1) h[i].push_back(0);
		ll y=pri[i];
		for(int e=2;x*y<=n/pri[i];++e)
		{
			y*=pri[i];
			if(h[i].size()==e)
			{
				ll f=F(pri[i],e),g=G(pri[i],1);
				for(int j=1;j<=e;++j) f-=g*h[i][e-j],g=G(pri[i],j+1);
				h[i].push_back(f);
			}
			dfs(i+1,x*y,w*h[i][e]);
		}
	}
}

代码中：

• ( exttt{F(x,e)}) 为 (F(x^e))
• ( exttt{G(x,e)}) 为 (G(x^e))
• ( exttt{sumG(x)}) 为 (sum_{i=1}^x G(i))